Approximating geometric bottleneck shortest paths

DOI10.1016/j.comgeo.2004.04.003zbMath1082.65015MaRDI 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

algorithms; shortest path

Mathematics Subject Classification ID

65K05: Numerical mathematical programming methods

90C20: Quadratic programming

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

Related Items

π/2-ANGLE YAO GRAPHS ARE SPANNERS, Spanning Properties of Yao and 𝜃-Graphs in the Presence of Constraints, On plane geometric spanners: a survey and open problems, On bounded degree plane strong geometric spanners, On a family of strong geometric spanners that admit local routing strategies, On bounded leg shortest paths problems, Continuous Yao graphs, The \(\varTheta_5\)-graph is a spanner, Shortest paths in intersection graphs of unit disks, Building Cartesian trees from free trees with \(k\) leaves, YAO GRAPHS SPAN THETA GRAPHS, DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE

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