A Unified Approach to Dynamic Point Location, Ray shooting, and Shortest Paths in Planar Maps

DOI10.1137/S0097539792224516MaRDI QIDQ4875452zbMATH OpenOpenAlexFDO

Authors Yi-Jen Chiang, Roberto Tamassia, F. P. Preparata

Publication date 2 July 1996

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

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

zbMATH Keywords

shortest-pathray-shooting queriespolylog-time dynamic data structure

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

• scientific article; zbMATH DE number 437528
• Dynamic Ray Shooting and Shortest Paths in Planar Subdivisions via Balanced Geodesic Triangulations
• Towards an optimal method for dynamic planar point location
• Dynamic planar point location with optimal query time

Cited in

(9)

• Dynamic Planar Point Location in External Memory.
• Dynamic Ray Shooting and Shortest Paths in Planar Subdivisions via Balanced Geodesic Triangulations
• Towards an optimal method for dynamic planar point location
• Relative convex hulls in semi-dynamic arrangements
• scientific article; zbMATH DE number 437528 (Why is no real title available?)
• I/O-efficient dynamic planar point location
• Union and split operations on dynamic trapezoidal maps
• Point Location in Incremental Planar Subdivisions.
• External memory planar point location with logarithmic updates

This page was built for publication: A Unified Approach to Dynamic Point Location, Ray shooting, and Shortest Paths in Planar Maps

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