Largest and Smallest Convex Hulls for Imprecise Points (2008)

Title Largest and Smallest Convex Hulls for Imprecise Points
Published in Algorithmica. ISSN 1432-0541.
Author Löffler, M.; Kreveld, Marc van
Date 2008
Reference(s) Computational geometry, Imprecision, Data imprecision, Convex hulls
Language English
Type Article
Publisher Springer
Abstract Assume that a set of imprecise points is given, where each point is specified by a region in which the point may lie. We study the problem of computing the smallest and largest possible convex hulls, measured by length and by area. Generally we assume the imprecision region to be a square, but we discuss the case where it is a segment or circle as well. We give polynomial time algorithms for several variants of this problem, ranging in running time from O(nlog n) to O(n13), and prove NP-hardness for some other variants.
Persistent Identifier URN:NBN:NL:UI:10-1874-30496
Metadata XML
Repository Utrecht University

Go to page top
Go back to contents
Go back to site navigation