Show simple item record

dc.contributor.authorHassanzadeh, Farzaden
dc.date2008-11-28 14:47:15.169
dc.date.accessioned2008-12-09T21:46:24Z
dc.date.available2008-12-09T21:46:24Z
dc.date.issued2008-12-09T21:46:24Z
dc.identifier.urihttp://hdl.handle.net/1974/1606
dc.descriptionThesis (Master, Computing) -- Queen's University, 2008-11-28 14:47:15.169en
dc.description.abstractThe 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.en
dc.format.extent408525 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoengen
dc.relation.ispartofseriesCanadian thesesen
dc.rightsThis 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.en
dc.subjectComputational Geometryen
dc.subjectConvex Hullen
dc.subjectImprecise Pointsen
dc.subjectApproximation Algorithmen
dc.titleMinimum Perimeter Convex Hull of a Set of Line Segments: An Approximationen
dc.typethesisen
dc.description.degreeM.Sc.en
dc.contributor.supervisorRappaport, Daviden
dc.contributor.departmentComputingen
dc.degree.grantorQueen's University at Kingstonen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record