Efficient Point Location in a Convex Spatial Cell-Complex

DOI10.1137/0221020zbMath0753.68094OpenAlexW2160212232MaRDI QIDQ3990653

Roberto Tamassia, Franco P. Preparata

Publication date: 28 June 1992

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0221020

zbMATH Keywords

point locationconvex cell complexpersistent trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items

Distance-sensitive planar point location ⋮ Linear data structures for fast ray-shooting amidst convex polyhedra ⋮ Vertical decompositions for triangles in 3-space ⋮ Towards an Optimal Method for Dynamic Planar Point Location ⋮ Dynamic reachability in planar digraphs with one source and one sink ⋮ Dynamic Planar Point Location in External Memory. ⋮ Dynamic Trees and Dynamic Point Location ⋮ Faster algorithms for growing prioritized disks and rectangles ⋮ Complexity of projected images of convex subdivisions