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

DOI10.1137/S0097539792224516zbMATH Open0841.68120OpenAlexW1981736066MaRDI QIDQ4875452FDOQ4875452

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

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)

Cited In (6)

• Dynamic Planar Point Location in External Memory.
• Towards an Optimal Method for Dynamic Planar Point Location
• Relative convex hulls in semi-dynamic arrangements
• I/O-efficient dynamic planar point location
• 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)