Date of Award

2003

Publication Type

Master Thesis

Degree Name

M.Sc.

Department

Computer Science

Keywords

Computer Science.

Supervisor

Mukhopadhyay, Asish,

Rights

info:eu-repo/semantics/openAccess

Abstract

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.) 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.

Download

Share

COinS