Approximating Largest Convex Hulls for Imprecise Points
Publication date
2008-12
Authors
van Kreveld, M.J.
Löffler, M.
Editors
Advisors
Supervisors
Document Type
Article
Metadata
Show full item recordCollections
License
taverne
Abstract
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
CG, IMP, CH, APPROX, Computational geometry, Data imprecision, Convex hul, Core-sets
Citation
Kreveld, M V & Löffler, M 2008, 'Approximating Largest Convex Hulls for Imprecise Points', Journal of Discrete Algorithms, vol. 6, no. 4, pp. 583-594. https://doi.org/10.1016/j.jda.2008.04.002