Study on the performance characteristics of convex hull algorithms

• Main Author: Khin Maung Aye.
• Other Authors: Tor, Shu Beng
• Format: Theses and Dissertations
• Language: English
• Published: 2008
• Subjects: DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
• Online Access: http://hdl.handle.net/10356/13443
• Institution: Nanyang Technological University

In this dissertation, the author has made an attempt to study the performance characteristics of various convex hull algorithms currently available. By definition, the convex hull of a set of points in a plane is the smallest convex polygon containing all the given points. Many convex hull algorithms exist in the computational geometry field. Some algorithms work better under certain circumstances when others perform better with totally different conditions. Literature survey of computational geometry and convex hull algorithms were carried out during the study on the performance characteristics of these algorithms. Each algorithm was studied both from time complexity and space complexity point of views. Most of the convex hull algorithms are usually found in papers published in technical journals rather than in textbooks. They are presented in several different forms such as using flow chart, pseudo code, or just description by words. Notation used and area of concentration also varies from one article to another. Pseudo code form, however, is the most preferred, but not always available.