Dynamic data structures for fat objects and their applications

DOI10.1007/3-540-63307-3_69zbMath1497.68525OpenAlexW1670028754MaRDI QIDQ5096947

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

Publication date: 19 August 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-63307-3_69

zbMATH Keywords

computational geometrydynamic data structurebinary space partitionquery pointquery cost

Mathematics Subject Classification ID

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

Related Items

On point covers of \(c-\)oriented polygons ⋮ Models and motion planning

Cites Work

• Unnamed Item
• Range searching with efficient hierarchical cuttings
• Four results on randomized incremental constructions
• Optimal packing and covering in the plane are NP-complete
• Maintenance of configurations in the plane
• Efficient partition trees
• Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
• Efficient hidden surface removal for objects with small union size
• Point location in fat subdivisions
• The complexity of the free space for a robot moving amidst fat obstacles
• Range searching in low-density environments
• 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects
• The complexity of the free space for motion planning amidst fat obstacles
• Dynamic half-space range reporting and its applications
• Computing depth orders for fat objects and related problems
• On the complexity of the union of fat convex objects in the plane
• Range Searching and Point Location among Fat Objects
• A Greedy Heuristic for the Set-Covering Problem
• Decomposable searching problems I. Static-to-dynamic transformation
• Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number
• An Output-Sensitive Convex Hull Algorithm for Planar Objects
• Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
• Applications of a semi-dynamic convex hull algorithm
• New results on binary space partitions in the plane (extended abstract)