Lower bounds for computing geometric spanners and approximate shortest paths

DOI10.1016/S0166-218X(00)00280-8zbMath0980.68119MaRDI QIDQ5936458

Michiel H. M. Smid, Danny Z. Chen, Gautam K. Das

Publication date: 2001

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

geometric spannersSteiner points

Mathematics Subject Classification ID

Trees (05C05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

A lower bound for computing geometric spanners, Geometric dilation of closed planar curves: New lower bounds, Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies, The Minimal Manhattan Network Problem in Three Dimensions

Cites Work

• Unnamed Item
• Unnamed Item
• Rectilinear shortest paths in the presence of rectangular barriers
• Constrained Delaunay triangulations
• \(L_ 1\) shortest paths among polygonal obstacles in the plane
• A sparse graph almost as good as the complete graph on points in \(k\) dimensions
• There are planar graphs almost as good as the complete graph
• Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
• CONSTRUCTING MULTIDIMENSIONAL SPANNER GRAPHS
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Planar spanners and approximate shortest path queries among obstacles in the plane