Computing the minimum perimeter triangle enclosing a convex polygon: Theory and implementation.

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 \u3c 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.) Paper copy at Leddy Library: Theses & Major Papers - Basement, West Bldg. / Call Number: Thesis2003 .M43. Source: Masters Abstracts International, Volume: 42-02, page: 0618. Adviser: Asish Mukhopadhyay. Thesis (M.Sc.)--University of Windsor (Canada), 2003