Fully Dynamic Point Location in a Monotone Subdivision

DOI10.1137/0218056MaRDI QIDQ4732115zbMATH OpenOpenAlexFDO

Authors Roberto Tamassia, F. 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 geometrydynamic data structuresmonotone polygonplanar subdivisionpoint location

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Dynamic Point Location in General Subdivisions
• DYNAMIZATION OF THE TRAPEZOID METHOD FOR PLANAR POINT LOCATION IN MONOTONE SUBDIVISIONS
• Towards an optimal method for dynamic planar point location
• New Results on Dynamic Planar Point Location
• Point location in dynamic planar subdivisions

Cited in

(22)

• Dynamic point location in arrangements of hyperplanes
• Visibility with a moving point of view
• Characterizing and efficiently computing quadrangulations of planar point sets
• A data structure for lattice representation
• Average case analysis of dynamic geometric optimization
• scientific article; zbMATH DE number 4211552 (Why is no real title available?)
• A new point-location algorithm and its practical efficiency: comparison with existing algorithms
• Optimal Point Location in a Monotone Subdivision
• scientific article; zbMATH DE number 140454 (Why is no real title available?)
• DYNAMIZATION OF THE TRAPEZOID METHOD FOR PLANAR POINT LOCATION IN MONOTONE SUBDIVISIONS
• Dynamic Trees and Dynamic Point Location
• Dynamic Point Location in General Subdivisions
• Towards an optimal method for dynamic planar point location
• Lower bounds for dynamic transitive closure, planar point location, and parentheses matching
• Quadrangulations of planar sets
• Dynamic Planar Point Location in External Memory.
• Point Location in Incremental Planar Subdivisions.
• Dynamic planar point location with optimal query time (extended abstract)
• External memory planar point location with logarithmic updates
• Dynamic reachability in planar digraphs with one source and one sink
• An incremental reconstruction method for dynamic planar point location
• Dynamic maintenance of planar digraphs, with applications

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

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