A New Approach to Planar Point Location

DOI10.1137/0210035zbMath0462.68048OpenAlexW2068376033MaRDI QIDQ3912042

Franco P. Preparata

Publication date: 1981

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

Full work available at URL: http://hdl.handle.net/2142/74214

zbMATH Keywords

planar graphsanalysis of algorithmscomputational geometry

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Discrete mathematics in relation to computer science (68R99)

Related Items (20)

New results on binary space partitions in the plane (extended abstract) ⋮ Adaptive Point Location in Planar Convex Subdivisions ⋮ Optimal randomized incremental construction for guaranteed logarithmic planar point location ⋮ New results on binary space partitions in the plane ⋮ A fast algorithm for point-location in a finite element mesh ⋮ Efficient binary space partitions for hidden-surface removal and solid modeling ⋮ Dynamic planar point location with optimal query time ⋮ Query point visibility computation in polygons with holes ⋮ \(L_ 1\) shortest paths among polygonal obstacles in the plane ⋮ A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING ⋮ Parallel batched planar point location on the CCC ⋮ Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection ⋮ Dynamic planar point location with optimal query time ⋮ An incremental reconstruction method for dynamic planar point location ⋮ Storing the subdivision of a polyhedral surface ⋮ Dynamic Trees and Dynamic Point Location ⋮ An optimal algorithm for constructing the weighted Voronoi diagram in the plane ⋮ Efficient visibility queries in simple polygons ⋮ On constant factors in comparison-based geometric algorithms and data structures ⋮ A workbench for computational geometry

This page was built for publication: A New Approach to Planar Point Location