An improved algorithm for shortest paths in weighted unit-disk graphs

DOI10.57717/CGT.V5I2.69MaRDI QIDQ6847364zbMATH OpenFDO

Authors Bruce W. Brewer, Haitao Wang

Publication date 9 March 2026

Published in CGT. Computing in Geometry and Topology (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.57717/CGT.V5I2.69

zbMATH Keywords

additively-weighted Voronoi diagramsdynamic nearest neighbor searchshortest pathsunit-disk graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• A sweepline algorithm for Voronoi diagrams
• Decomposable searching problems
• Dynamic geometric data structures via shallow cuttings
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• Hopcroft's problem, log* shaving, two-dimensional fractional cascading, and decision trees
• scientific article; zbMATH DE number 6861957 (Why is no real title available?)
• Near-optimal algorithms for shortest paths in weighted unit-disk graphs
• Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
• On bounded leg shortest paths problems
• Optimal Point Location in a Monotone Subdivision
• Optimal Search in Planar Subdivisions
• Shortest paths in intersection graphs of unit disks
• The design of dynamic data structures

This page was built for publication: An improved algorithm for shortest paths in weighted unit-disk graphs

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