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.

slides

Journal Article (peer-reviewed)

Conference Proceedings (peer-reviewed)

Technical Report (not reviewed)

back to list