Approximating Largest Convex Hulls for Imprecise Points

Marc van Kreveld; Maarten Löffler

doi:10.1016/j.jda.2008.04.002

Approximating Largest Convex Hulls for Imprecise Points

Marc van Kreveld^*, Maarten Löffler^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › Academic › peer-review

1 Downloads (Pure)

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.

Original language	English
Pages (from-to)	583-594
Number of pages	12
Journal	Journal of Discrete Algorithms
Volume	6
Issue number	4
DOIs	https://doi.org/10.1016/j.jda.2008.04.002
Publication status	Published - Dec 2008

Keywords

CG, IMP, CH, APPROX
Computational geometry
Data imprecision
Convex hul
Core-sets

Access to Document

10.1016/j.jda.2008.04.002

1-s2.0-S1570866708000403-mainFinal published version, 549 KBLicence: Taverne

Cite this

@article{865e13ce865a4f388eac9805e455a4a4,

title = "Approximating Largest Convex Hulls for Imprecise Points",

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",

author = "Kreveld, {Marc van} and Maarten L{\"o}ffler",

year = "2008",

month = dec,

doi = "10.1016/j.jda.2008.04.002",

language = "English",

volume = "6",

pages = "583--594",

journal = "Journal of Discrete Algorithms",

issn = "1570-8667",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - Approximating Largest Convex Hulls for Imprecise Points

AU - Kreveld, Marc van

AU - Löffler, Maarten

PY - 2008/12

Y1 - 2008/12

N2 - 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.

AB - 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.

KW - CG, IMP, CH, APPROX

KW - Computational geometry

KW - Data imprecision

KW - Convex hul

KW - Core-sets

U2 - 10.1016/j.jda.2008.04.002

DO - 10.1016/j.jda.2008.04.002

M3 - Article

SN - 1570-8667

VL - 6

SP - 583

EP - 594

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

IS - 4

ER -

Approximating Largest Convex Hulls for Imprecise Points

Abstract

Keywords

Access to Document

Fingerprint

Cite this