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 - http://www.scopus.com/inward/record.url?scp=0012741558&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0012741558&partnerID=8YFLogxK
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 -