On geometric optimization problems

Abstract

A number of geometric optimization problems are studied in this dissertation. Specifically, we consider the polygonal path approximation problem the optimal penetration problem and a related sum of linear fractionals problem. These problems find applications in many fields, such as robotics, computer graphics, computer vision, medical imaging, geographical information systems, VLSI layout, plant and facility layout and operations research. We present efficient algorithms for solving these problems that are either the first ones, or they are significant improvements over the previously best known algorithms. Most of our algorithms are based on new ideas and techniques, and involve novel geometric observations.