Dynamic data structures for fat objects and their applications

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

Research output: Contribution to journalArticlepeer-review

38 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)215-227
Number of pages13
JournalComputational Geometry: Theory and Applications
Volume15
Issue number4
DOIs
StatePublished - Apr 2000
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Dynamic data structures for fat objects and their applications'. Together they form a unique fingerprint.

Cite this