## Approximating Largest Convex Hulls for Imprecise Points

Assume that a set of imprecise points in the plane is given, where each point is specified by a region in which the point will lie. Such a region can be modelled as a circle, square, line segment, etc. We study the problem of maximising the area of the convex hull of such a set. We prove NP-hardness when the imprecise points are modelled as line segments, and give linear time approximation schemes for a variety of models, based on the core-set paradigm.

keywords: Approximation, Computational Geometry, Convex Hulls, Data Imprecision

### Journal Article (peer-reviewed)

Maarten Löffler, Marc van Kreveld

Approximating Largest Convex Hulls for Imprecise Points

Journal of Discrete Algorithms

6, 4, 583–594, 2008

### Conference Proceedings (peer-reviewed)

Maarten Löffler, Marc van Kreveld

Approximating Largest Convex Hulls for Imprecise Points

Proc. 5th Workshop on Approximation and Online Algorithms

LNCS 4927, 89–102, 2008

*Invited to Special Issue of TCS*

### Technical Report (not reviewed)

Maarten Löffler, Marc van Kreveld

Approximating Largest Convex Hulls for Imprecise Points

UU-CS-2007-038, 2007

back to list