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. / Thesis (Master, Computing) -- Queen's University, 2008-11-28 14:47:15.169
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OKQ.1974/1606 |
| Date | 09 December 2008 |
| Creators | Hassanzadeh, Farzad |
| Contributors | Queen's University (Kingston, Ont.). Theses (Queen's University (Kingston, Ont.)) |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Format | 408525 bytes, application/pdf |
| Rights | 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. |
| Relation | Canadian theses |
Page generated in 0.0018 seconds