| Geometric optimization, an important field of computational geometry, finds the best possible solution to a computational problem that involves geometric objects. An attractive fundamental problem in this area is one of approximating a convex n-gon with a simpler convex k-gon, where k < n, and the area or the perimeter of the approximate object is minimized. This problem arises in a wide range of applications, such as geographic information systems (GIS), spatial databases, pattern recognition, and computer graphics, to name but a few. The approximation of convex polygons with their respective enclosing triangles is a particularly interesting problem; however, finding an optimal linear time solution for computing the minimum perimeter triangle enclosing a convex polygon was a long-standing open problem, which turned out to be more difficult than determining an enclosing triangle of minimal area.; In this thesis, we suggest some theoretical and practical justifications for the linear time complexity of a recently proposed optimal solution and provide an efficient and robust implementation of that solution. (Abstract shortened by UMI.)... |
