Two- and three- dimensional point location in rectangular subdivisions

DOI10.1007/3-540-55706-7_32MaRDI QIDQ5056154zbMATH OpenOpenAlexFDO

Authors Jack Snoeyink, Mark de Berg, Marc Van Kreveld

Publication date 9 December 2022

Published in Algorithm Theory — SWAT '92 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-55706-7_32

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 140454
• Orthogonal point location and rectangle stabbing queries in 3-d
• Point location in fat subdivisions
• Dynamic Point Location in General Subdivisions
• I/O-Efficient Point Location in a Set of Rectangles

Cites work

• A priority queue in which initialization and queue operations takeO(loglogD) time
• A space-optimal solution of general region location
• Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
• Bounded ordered dictionaries in O(log log N) time and O(n) space
• Design and implementation of an efficient priority queue
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Filtering Search: A New Approach to Query-Answering
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• Log-logarithmic worst-case range queries are possible in space theta(N)
• PLANAR POINT LOCATION REVISITED
• Preserving order in a forest in less than logarithmic time and linear space
• Storing a Sparse Table with 0 (1) Worst Case Access Time

Cited in

(5)

• Point location in fat subdivisions
• The point-location problem for three-dimensional space
• scientific article; zbMATH DE number 140454 (Why is no real title available?)
• Point Location in Incremental Planar Subdivisions.
• Adaptive Point Location in Planar Convex Subdivisions

This page was built for publication: Two- and three- dimensional point location in rectangular subdivisions

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