Minimum Perimeter Convex Hull of a Set of Line Segments: An Approximation
Loading...
Authors
Hassanzadeh, Farzad
Date
2008-12-09T21:46:24Z
Type
thesis
Language
eng
Keyword
Computational Geometry , Convex Hull , Imprecise Points , Approximation Algorithm
Alternative Title
Abstract
The problem of finding the convex hull of a set of points in the plane is one of the fundamental and well-studied problems in Computational Geometry. However, for a set of imprecise points, the convex hull problem has not been thoroughly investigated. By imprecise points, we refer to a region in the plane inside which one point may lie. We are particularly interested in finding a minimum perimeter convex hull of a set of imprecise points, where the imprecise points are modelled as line segments. Currently, the best known algorithm that solves the minimum perimeter convex hull problem has an exponential running time in the worst case. It is still unknown whether this problem is NP-hard. We explore several approximation algorithms for this problem. Finally we propose a constant factor approximation algorithm that runs in O(nlogn) time.
Description
Thesis (Master, Computing) -- Queen's University, 2008-11-28 14:47:15.169
Citation
Publisher
License
This publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.