Tight stretch factors for \(L_1\)- and \(L_\infty\)-Delaunay triangulations

DOI10.1016/j.comgeo.2014.10.005zbMath1305.65097MaRDI QIDQ482347

Ljubomir Perković, Nicolas Bonichon, Nicolas Hanusse, Cyril Gavoille

Publication date: 23 December 2014

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

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

zbMATH Keywords

Delaunay triangulation; \(L_p\)-metric; geometric spanner; stretch factor

Mathematics Subject Classification ID

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

Related Items

Unnamed Item, Improved routing on the Delaunay triangulation, Improved bounds on the stretch factor of \(Y_{4}\), Upper and lower bounds for online routing on Delaunay triangulations, Emanation graph: a plane geometric spanner with Steiner points, Veering triangulations and Cannon–Thurston maps

Cites Work

• Unnamed Item
• Unnamed Item
• Delaunay graphs are almost as good as complete graphs
• Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
• Classes of graphs which approximate the complete Euclidean graph
• There are planar graphs almost as good as the complete graph
• Competitive online routing in geometric graphs
• Bounding the locality of distributed routing algorithms
• Triangulations and applications
• The Stretch Factor of the Delaunay Triangulation Is Less than 1.998
• On the stretch factor of convex Delaunay graphs
• π/2-ANGLE YAO GRAPHS ARE SPANNERS