New Results on Dynamic Planar Point Location

DOI10.1137/0221057zbMath0756.68092OpenAlexW2148069113MaRDI QIDQ4015978

Siu-Wing Cheng, Ravi Janardan

Publication date: 6 December 1992

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

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

zbMATH Keywords

point locationplanar subdivisionpriority searchtrees of bounded balance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

I/O-efficient dynamic planar point location ⋮ Linear-time construction of treaps and Cartesian trees ⋮ Quadrangulations of planar sets ⋮ Towards an Optimal Method for Dynamic Planar Point Location ⋮ Characterizing and efficiently computing quadrangulations of planar point sets ⋮ Incremental hive graph ⋮ A faster algorithm for computing motorcycle graphs ⋮ Bottleneck detour tree of points on a path ⋮ Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os ⋮ INTERSECTION PROBLEMS ON SEGMENTS UNDER BOUNDARY UPDATES WITH APPLICATION TO PERSISTENT LISTS ⋮ Computing shortest heterochromatic monotone routes ⋮ Unnamed Item ⋮ External memory planar point location with logarithmic updates ⋮ Point Location in Incremental Planar Subdivisions. ⋮ Dynamic Planar Point Location in External Memory. ⋮ Dynamic Trees and Dynamic Point Location ⋮ Succinct and Implicit Data Structures for Computational Geometry

This page was built for publication: New Results on Dynamic Planar Point Location