## Largest and Smallest Convex Hulls for Imprecise Points

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*(*n*log*n*) to *O*(*n*^{13}), and prove NP-hardness for some other variants.

keywords: Computational Geometry, Convex Hulls, Data Imprecision

### Journal Article (peer-reviewed)

Maarten Löffler, Marc van Kreveld

Largest and Smallest Convex Hulls for Imprecise Points

Algorithmica

56, 2, 235–269, 2010

### Conference Proceedings (peer-reviewed)

Maarten Löffler, Marc van Kreveld

Largest and Smallest Tours and Convex Hulls for Imprecise Points

Proc. 10th Scandinavian Workshop on Algorithm Theory

LNCS 4059, 375–387, 2006

### Workshop or Poster (weakly reviewed)

Maarten Löffler, Marc van Kreveld

Largest and Smallest Tours and Convex Hulls for Imprecise Points

Proc. 12th Conf. Advanced School for Computing and Imaging

333–340, 2006

### Technical Report (not reviewed)

Maarten Löffler, Marc van Kreveld

Largest and Smallest Convex Hulls for Imprecise Points

UU-CS-2006-019, 2006

back to list