Dynamic data structures for fat objects and their applications

Alon Efrat; Matthew J. Katz; Frank Nielsen; Micha Sharir

doi:10.1016/S0925-7721(99)00059-0

Dynamic data structures for fat objects and their applications

Alon Efrat
, Matthew J. Katz
, Frank Nielsen
, Micha Sharir

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

48 Scopus citations

Abstract

We present several efficient dynamic data structures for point-enclosure queries, involving convex fat objects in ℝ² or ℝ³. Our planar structures are actually fitted for a more general class of objects - (β, δ)-covered objects -which are not necessarily convex, see definition below. These structures are more efficient than alternative known structures, because they exploit the fatness of the objects. We then apply these structures to obtain efficient solutions to two problems: (i) finding a perfect containment matching between a set of points and a set of convex fat objects, and (ii) finding a piercing set for a collection of convex fat objects, whose size is optimal up to some constant factor.

Original language	English (US)
Pages (from-to)	215-227
Number of pages	13
Journal	Computational Geometry: Theory and Applications
Volume	15
Issue number	4
DOIs	https://doi.org/10.1016/S0925-7721(99)00059-0
State	Published - Apr 2000
Externally published	Yes

Keywords

Containment matching
Dynamic data structure
Fat objects
Piercing set
Point enclosure

ASJC Scopus subject areas

Computer Science Applications
Geometry and Topology
Control and Optimization
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1016/S0925-7721(99)00059-0

Cite this

@article{f60a08d65faa42d39885820cc8b046d9,

title = "Dynamic data structures for fat objects and their applications",

abstract = "We present several efficient dynamic data structures for point-enclosure queries, involving convex fat objects in ℝ2 or ℝ3. Our planar structures are actually fitted for a more general class of objects - (β, δ)-covered objects -which are not necessarily convex, see definition below. These structures are more efficient than alternative known structures, because they exploit the fatness of the objects. We then apply these structures to obtain efficient solutions to two problems: (i) finding a perfect containment matching between a set of points and a set of convex fat objects, and (ii) finding a piercing set for a collection of convex fat objects, whose size is optimal up to some constant factor.",

keywords = "Containment matching, Dynamic data structure, Fat objects, Piercing set, Point enclosure",

author = "Alon Efrat and Katz, \{Matthew J.\} and Frank Nielsen and Micha Sharir",

note = "Funding Information: I A preliminary version of this paper appeared as [14]. ∗Corresponding author. E-mail addresses: [email protected] (M.J. Katz), [email protected] (A. Efrat), [email protected] (F. Nielsen), [email protected] (M. Sharir). 1Supported by the Israel Science Foundation founded by the Israel Academy of Sciences and Humanities. 2Supported by NSF Grant CCR-97-32101, by a grant from the U.S.–Israeli Binational Science Foundation, by the ESPRIT IV LTR project No. 21957 (CGAL), and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University.",

year = "2000",

month = apr,

doi = "10.1016/S0925-7721(99)00059-0",

language = "English (US)",

volume = "15",

pages = "215--227",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

T1 - Dynamic data structures for fat objects and their applications

AU - Efrat, Alon

AU - Katz, Matthew J.

AU - Nielsen, Frank

AU - Sharir, Micha

N1 - Funding Information: I A preliminary version of this paper appeared as [14]. ∗Corresponding author. E-mail addresses: [email protected] (M.J. Katz), [email protected] (A. Efrat), [email protected] (F. Nielsen), [email protected] (M. Sharir). 1Supported by the Israel Science Foundation founded by the Israel Academy of Sciences and Humanities. 2Supported by NSF Grant CCR-97-32101, by a grant from the U.S.–Israeli Binational Science Foundation, by the ESPRIT IV LTR project No. 21957 (CGAL), and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University.

PY - 2000/4

Y1 - 2000/4

N2 - We present several efficient dynamic data structures for point-enclosure queries, involving convex fat objects in ℝ2 or ℝ3. Our planar structures are actually fitted for a more general class of objects - (β, δ)-covered objects -which are not necessarily convex, see definition below. These structures are more efficient than alternative known structures, because they exploit the fatness of the objects. We then apply these structures to obtain efficient solutions to two problems: (i) finding a perfect containment matching between a set of points and a set of convex fat objects, and (ii) finding a piercing set for a collection of convex fat objects, whose size is optimal up to some constant factor.

AB - We present several efficient dynamic data structures for point-enclosure queries, involving convex fat objects in ℝ2 or ℝ3. Our planar structures are actually fitted for a more general class of objects - (β, δ)-covered objects -which are not necessarily convex, see definition below. These structures are more efficient than alternative known structures, because they exploit the fatness of the objects. We then apply these structures to obtain efficient solutions to two problems: (i) finding a perfect containment matching between a set of points and a set of convex fat objects, and (ii) finding a piercing set for a collection of convex fat objects, whose size is optimal up to some constant factor.

KW - Containment matching

KW - Dynamic data structure

KW - Fat objects

KW - Piercing set

KW - Point enclosure

UR - https://www.scopus.com/pages/publications/0012741558

UR - https://www.scopus.com/pages/publications/0012741558#tab=citedBy

U2 - 10.1016/S0925-7721(99)00059-0

DO - 10.1016/S0925-7721(99)00059-0

M3 - Article

AN - SCOPUS:0012741558

SN - 0925-7721

VL - 15

SP - 215

EP - 227

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 4

ER -

Dynamic data structures for fat objects and their applications

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this