Dynamic data structures for fat objects and their applications

DOI10.1016/S0925-7721(99)00059-0MaRDI QIDQ1975962zbMATH OpenFDO

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

Publication date 8 May 2000

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0925-7721(99)00059-0

zbMATH Keywords

point-enclosure queries

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Dynamic data structures for fat objects and their applications
• Range Searching and Point Location among Fat Objects
• 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects
• Vertical ray shooting for fat objects

Cited in

(21)

• Contraction and expansion of convex sets
• Fast stabbing of boxes in high dimensions
• Models and motion planning
• Approximate unions of lines and Minkowski sums
• Polynomial-time approximation schemes for piercing and covering with applications in wireless networks
• SKIP QUADTREES: DYNAMIC DATA STRUCTURES FOR MULTIDIMENSIONAL POINT SETS
• Range Searching and Point Location among Fat Objects
• A note about weak -nets for axis-parallel boxes in d-space
• Approximation algorithms for maximum independent set of pseudo-disks
• Dynamic data structures for fat objects and their applications
• Guard Files: Stabbing and Intersection Queries on Fat Spatial Objects
• Exact and approximation algorithms for computing optimal fat decompositions
• Online geometric covering and piercing
• New lower bound and algorithm for online geometric hitting set problem
• A quadtree, a Steiner spanner, and approximate nearest neighbours in hyperbolic space
• Fully dynamic maximum independent sets of disks in polylogarithmic update time
• Online geometric hitting set using points in \(\mathbb{Z}^d\)
• Fully dynamic maximum independent sets of disks in polylogarithmic update time
• Dynamic streaming algorithms for geometric independent set
• Sparse bounded hop-spanners for geometric intersection graphs
• Generalized disk graphs

Describes a project that uses

Uses Software

• Hull

This page was built for publication: Dynamic data structures for fat objects and their applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1975962)