On solving geometric optimization problems using shortest paths
Elefterios A. Melissaratos, Diane L. Souvaine · 1990
We have developed techniques which contribute to efficient algorithms for certain geometric optimization problems involving simple polygons: computing minimum separators, maximum inscribed triangles, a minimum circumscribed concave quadrilateral, or a maximum contained triangle.The structure for our algorithms is as follows: a) decompose the initial problem into a low-degree polynomial number of easy optimization problems; b) solve each individual subproblem in constant time using the methods of cealcu-Ins, standard methods of numerical analysis, or linear programming.The decomposition step uses shorteat path trees inside simple polygons (Guibas et. al.~ 1987) and, in the case of inscribed triangles, produces a new class of polygons, the fan-shaped polygon.By extending the shortest-path algorithm to splinegons, we also generate splinegon-versions of the algorithms for some of the optimization problems.The problems we discuss fall into four subgroups: Separators: If two points z and y lie on the boundary of simple polygon P and define a directed line segment zy C_ P that separates P into two sets PL and Pa, then zy is called a separator.M i n i m u m l e n g t h : The areas of PL and PR are defined by constants KL and KR.Find a separator of minimum length.