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

Loading...
Thumbnail Image

Authors

Hassanzadeh, Farzad

Date

2008-12-09T21:46:24Z

Type

thesis

Language

eng

Keyword

Computational Geometry , Convex Hull , Imprecise Points , Approximation Algorithm

Research Projects

Organizational Units

Journal Issue

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.

Journal

Volume

Issue

PubMed ID

External DOI

ISSN

EISSN