Dynamic Trees and Dynamic Point Location

DOI10.1137/S0097539793254376zbMath0915.68162MaRDI QIDQ4210167

Roberto Tamassia, Michael T. Goodrich

Publication date: 21 September 1998

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

zbMATH Keywords

on-line algorithmscomputational geometrypoint locationdynamic data structurescentroid decomposition

Mathematics Subject Classification ID

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

Related Items

Distance-sensitive planar point location, Towards an Optimal Method for Dynamic Planar Point Location, The maximin line problem with regional demand, Shape matching under rigid motion, On the computation of an arrangement of quadrics in 3D, Computing shortest heterochromatic monotone routes, Point Location in Incremental Planar Subdivisions., Dynamic Planar Point Location in External Memory.

Cites Work

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