Paper: Dynamic Data Structures for Fat Objects and Their Applications

Dynamic Data Structures for Fat Objects and Their Applications

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

Abstract:
We present several efficient dynamic data structures for point-enclosure queries, involving convex fat objects in R² or R³. 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 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,
(ii) Finding a piercing set for a collection of convex fact objects, whose size is optimal up to some constant factor.

Key words: fat objects, dynamic data structure, point enclosure, containment matching, piercing set.

Get the paper here.

The original publication is available at Elsevier Science.

Ask the PDF paper here (284 Kb size, 16 pages, 3 figures) © Elsevier Science.

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

Bibtex entry:


@Article{ekns-ddsfo:2000
	, author =	"Alon Efrat and Mstthew J. Katz and Frank Nielsen and Micha Sharir"
	, title =	"Dynamic Data Structures for Fat Objects and Their Applications"
	, journal =	"Comput. Geom. Theory Appl."
	, volume =	15
	, number =	4
	, year =	2000
	, pages =	"215-227"
	, doi = {10.1016/S0925-7721(99)00059-0}
 }


@InProceedings{ekns-ddsfo:1997
	, author =	"Alon Efrat and Matthew J. Katz and Frank Nielsen and Micha Sharir"
	, title =	"Dynamic Data Structures for Fat Objects and Their Applications"
	, booktitle =	"Proc. 5th Workshop Algorithms Data Struct."
	, year =	1997
	, pages =	"297--306"
}

Related publications:

Alon Efrat, Matthew J. Katz, Frank Nielsen and Micha Sharir,
Dynamic Data Structures For Fat Objects and Their Applications,
Computational Geometry: Theory and Its Applications (CGTA), Elsevier,
Volume 15, Number 4, pp. 215-227, 2000.
Alon Efrat, Matthew J. Katz, Frank Nielsen and Micha Sharir,
Dynamic Data Structures For Fat Objects and Their Applications,
Workshop on Algorithms and Data-Structures (WADS),
Springer Verlag Lecture Notes in Computer Science (LNCS),
Volume 1272, pp. 297-306, 1997.

Last updated, 2003.