Dynamic Trees and Dynamic Point Location

DOI10.1137/S0097539793254376zbMATHMaRDI QIDQ4210167FDO

Authors Roberto Tamassia, Michael T. Goodrich

Publication date 21 September 1998

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

zbMATH Keywords

computational geometrypoint locationon-line algorithmsdynamic data structurescentroid decomposition

Mathematics Subject Classification ID

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

Recommendations

• Dynamic Point Location in General Subdivisions
• Fully Dynamic Point Location in a Monotone Subdivision
• New Results on Dynamic Planar Point Location

Cites work

• scientific article; zbMATH DE number 4037201 (Why is no real title available?)
• A New Approach to Planar Point Location
• A balanced search tree O(1) worst-case update time
• A data structure for dynamic trees
• Adding range restriction capability to dynamic data structures
• Dynamic planar point location with optimal query time
• Efficient Point Location in a Convex Spatial Cell-Complex
• Fractional cascading. I: A data structuring technique
• Fractional cascading. II: Applications
• Fully Dynamic Point Location in a Monotone Subdivision
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Location of a Point in a Planar Subdivision and Its Applications
• Maintenance of a minimum spanning forest in a dynamic plane graph
• New Results on Dynamic Planar Point Location
• Optimal Point Location in a Monotone Subdivision
• Optimal Search in Planar Subdivisions
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Priority Search Trees
• Searching and storing similar lists
• Triangulating a simple polygon
• Triangulating a simple polygon in linear time
• Visibility and intersection problems in plane geometry

Cited in

(14)

• The maximin line problem with regional demand
• scientific article; zbMATH DE number 1617247 (Why is no real title available?)
• Computing shortest heterochromatic monotone routes
• Distance-sensitive planar point location
• Shape matching under rigid motion
• Dynamic Planar Point Location in External Memory.
• Towards an optimal method for dynamic planar point location
• Dynamic partition trees
• Point Location in Incremental Planar Subdivisions.
• scientific article; zbMATH DE number 742971 (Why is no real title available?)
• On the dynamization of data structures
• New Results on Dynamic Planar Point Location
• On the computation of an arrangement of quadrics in 3D
• Dynamic Point Location in General Subdivisions

This page was built for publication: Dynamic Trees and Dynamic Point Location

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