Invited Session Thu.3.H 3004

Thursday, 15:15 - 16:45 h, Room: H 3004

Cluster 2: Combinatorial optimization [...]

Optimization methods for geometric problems


Chair: Sándor P. Fekete and Alexander Kröller



Thursday, 15:15 - 15:40 h, Room: H 3004, Talk 1

Dan Halperin
Multi-objective path optimization in motion planning: From the particular to the general


When planning collision-free paths for mobile objects
(robots or other creatures) in environments cluttered with
obstacles, it is often desirable to simultaneously consider
several path-quality criteria. We start with a combination
of criteria, which is commonplace in this setting: length
and clearance. Namely, we wish that the path will be short
and the moving object will be well away from the obstacles.
We review several planning techniques specifically tailored
to optimizing this combination. We then move on to a
general optimization technique that can simultaneously
address a large variety of objectives and does not assume
any specific path-planning approach. It is based on a
simple path-hybridization method, it is easy to implement,
and it has proved itself highly effective for a wide range
of problems, as we shall demonstrate.



Thursday, 15:45 - 16:10 h, Room: H 3004, Talk 2

Cid Carvalho de Souza
Towards solving to optimality the art gallery with point-guards problem

Coauthors: Pedro J. de Rezende, Davi C. Tozoni


We present our progress towards the development of an exact and effective algorithm to solve the NP-hard art gallery with point-guards problem (AGPG). A set of points is said to cover a polygon P if the union of their visibility polygons is P. In AGPG, one seeks a minimum-sized set of points in P that covers P. Despite its theoretical complexity, we give experimental evidence that AGPG can be solved to proven optimality even for large sized instances of a thousand vertices. To this end, we developed an algorithm which iteratively produces lower and upper bounds on the number of guards needed to cover P. These bounds are computed via integer programming models and rely on a theoretical result showing that for a finite set W of witnesses in P there exists an optimal solution covering W for which the guards belong to a well-defined set of points whose size is polynomial in |W|. We tested this algorithm on a benchmark composed of several classes of polygons of various sizes, all of which obtained from the literature. Our algorithm solves most of these instances in only tens of minutes in a standard desktop computer.



Thursday, 16:15 - 16:40 h, Room: H 3004, Talk 3

Alexander Kröller
Practical solutions and bounds for art gallery problems

Coauthors: Tobias Baumgartner, Sándor P. Fekete, Mahdi Moeini, Christiane Schmidt


The classical Art gallery problem asks for the minimum number of guards that achieve visibility coverage of a given polygon. It is known to be NP-hard, even for very restricted and discrete special cases. Even though the it has been extensively studied in almost 40 years, practical algorithms to find optimal solutions or almost-optimal bounds are not known. We present a primal-dual algorithm based on mathematical programming, which provides lower bounds on the necessary number of guards and - in case of convergence and integrality - ends with an optimal solution. It has been implemented and extensively tested on different classes of polygons; experimental results will be discussed. Additionally we show how to extend the procedure to practical applications of the Art Gallery Problem. These occur in laser scanning of buildings, but come with additional constraints - such as limited viewing range and loss in quality over distances.


  payday loans online. This pill gives a hand to thousands who suffer from erectile dysfunction. People who take Viagra Super Active can forget about their impotence and have a normal intimate life.