Minimum Perimeter Convex Hull of a Set of Line Segments: An Approximation

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 [14]. 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(n log n) time. i Acknowledgements I would like to dedicate this work to my family who has supported me through all stages of my life. I am grateful to my supervisor, David Rappaport, who has provided support and guidance throughout my education at Queen’s. I would also like to thank my friends, without whom, I would not have had such an amazing experience in Kingston. Last but not least, I would like to thank the Queen’s community for providing me with this great opportunity. i