Study on the performance characteristics of convex hull algorithms

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

Full description

Saved in:
Bibliographic Details
Main Author: Khin Maung Aye.
Other Authors: Tor, Shu Beng
Format: Theses and Dissertations
Language:English
Published: 2008
Subjects:
Online Access:http://hdl.handle.net/10356/13443
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary: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.