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

DOI10.1016/j.comgeo.2014.10.005zbMath1305.65097OpenAlexW2963981923MaRDI 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\)-metricgeometric spannerstretch factor

Mathematics Subject Classification ID

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

Related Items (6)

Improved bounds on the stretch factor of \(Y_{4}\) ⋮ Upper and lower bounds for online routing on Delaunay triangulations ⋮ Improved routing on the Delaunay triangulation ⋮ Unnamed Item ⋮ 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

This page was built for publication: Tight stretch factors for \(L_1\)- and \(L_\infty\)-Delaunay triangulations