Approximating geometric bottleneck shortest paths

DOI10.1016/j.comgeo.2004.04.003zbMath1082.65015OpenAlexW3021208656MaRDI QIDQ1886239

Anil Maheshwari, Giri Narasimhan, Norbert Zeh, Prosenjit Bose, Michiel H. M. Smid

Publication date: 18 November 2004

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2004.04.003

zbMATH Keywords

algorithmsshortest path

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Quadratic programming (90C20) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items

YAO GRAPHS SPAN THETA GRAPHS ⋮ On plane geometric spanners: a survey and open problems ⋮ Continuous Yao graphs ⋮ On bounded leg shortest paths problems ⋮ On bounded degree plane strong geometric spanners ⋮ Building Cartesian trees from free trees with \(k\) leaves ⋮ Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time ⋮ π/2-ANGLE YAO GRAPHS ARE SPANNERS ⋮ The \(\varTheta_5\)-graph is a spanner ⋮ On a family of strong geometric spanners that admit local routing strategies ⋮ On the restricted 1-Steiner tree problem ⋮ Spanning Properties of Yao and 𝜃-Graphs in the Presence of Constraints ⋮ Unnamed Item ⋮ DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE ⋮ On the restricted \(k\)-Steiner tree problem ⋮ Odd Yao-Yao Graphs are Not Spanners ⋮ Shortest paths in intersection graphs of unit disks

Cites Work

• An optimal algorithm for constructing oriented Voronoi diagrams and geograph neighborhood graphs
• Classes of graphs which approximate the complete Euclidean graph
• Fast Algorithms for Finding Nearest Common Ancestors
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item