Fully Dynamic Point Location in a Monotone Subdivision

DOI10.1137/0218056zbMath0682.68056OpenAlexW2017351109MaRDI QIDQ4732115

Roberto Tamassia, Franco P. Preparata

Publication date: 1989

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

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

zbMATH Keywords

analysis of algorithmscomputational geometrypoint locationdynamic data structuresplanar subdivisionmonotone polygon

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (14)

Lower bounds for dynamic transitive closure, planar point location, and parentheses matching ⋮ Quadrangulations of planar sets ⋮ Towards an Optimal Method for Dynamic Planar Point Location ⋮ Average case analysis of dynamic geometric optimization ⋮ Characterizing and efficiently computing quadrangulations of planar point sets ⋮ A data structure for lattice representation ⋮ Dynamic maintenance of planar digraphs, with applications ⋮ Dynamic point location in arrangements of hyperplanes ⋮ Dynamic reachability in planar digraphs with one source and one sink ⋮ An incremental reconstruction method for dynamic planar point location ⋮ Point Location in Incremental Planar Subdivisions. ⋮ Dynamic Planar Point Location in External Memory. ⋮ Dynamic Trees and Dynamic Point Location ⋮ Visibility with a moving point of view

This page was built for publication: Fully Dynamic Point Location in a Monotone Subdivision