Dynamic data structures for fat objects and their applications

DOI10.1007/3-540-63307-3_69MaRDI QIDQ5096947zbMATH OpenOpenAlexFDO

Authors 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

binary space partitioncomputational geometrydynamic data structurequery costquery point

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
• 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects
• Polynomial-time approximation schemes for packing and piercing fat objects
• Range Searching and Point Location among Fat Objects
• Vertical ray shooting for fat objects

Cites work

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

Cited in

(6)

• Dynamic data structures for fat objects and their applications
• Range Searching and Point Location among Fat Objects
• Models and motion planning
• Guard Files: Stabbing and Intersection Queries on Fat Spatial Objects
• Vertical ray shooting for fat objects
• On point covers of c-oriented polygons

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 Q5096947)