Tight stretch factors for L₁- and L_-Delaunay triangulations

DOI10.1016/J.COMGEO.2014.10.005zbMATH Open1305.65097OpenAlexW2963981923MaRDI QIDQ482347FDOQ482347

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

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

Recommendations

• The stretch factor of \(L _{1}\)- and \(L _{ \infty }\)-Delaunay triangulations
• Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
• Improved stretch factor of Delaunay triangulations of points in convex position
• The stretch factor of the Delaunay triangulation is less than 1.998
• Improved stretch factor of Delaunay triangulations of points in convex position

zbMATH Keywords

Delaunay triangulation\(L_p\)-metricgeometric spannerstretch factor

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• There are planar graphs almost as good as the complete graph
• Delaunay graphs are almost as good as complete graphs
• Classes of graphs which approximate the complete Euclidean graph
• \(\pi /2\)-angle Xao graphs are spanners
• Competitive routing in the half-\(\theta_6\)-graph
• Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
• On the stretch factor of convex Delaunay graphs
• Bounding the locality of distributed routing algorithms
• Competitive online routing in geometric graphs
• Triangulations and applications
• The stretch factor of the Delaunay triangulation is less than 1.998

Cited In (16)

• Veering triangulations and Cannon-Thurston maps
• The stretch factor of \(L _{1}\)- and \(L _{ \infty }\)-Delaunay triangulations
• Improved upper bound on the stretch factor of Delaunay triangulations
• Improved routing on the Delaunay triangulation
• The stretch factor of the Delaunay triangulation is less than 1.998
• Linear elasticity of planar Delaunay networks. II: Voigt and Reuss bounds, and modification for centroids
• Upper and lower bounds for online routing on Delaunay triangulations
• Improved stretch factor of Delaunay triangulations of points in convex position
• The Stretch Factor of Hexagon-Delaunay Triangulations
• Improved bounds on the stretch factor of \(Y_{4}\)
• Improved routing on the Delaunay triangulation
• Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
• On the stretch factor of Delaunay triangulations of points in convex position
• The stretch factor of hexagon-Delaunay triangulations
• Emanation graph: a plane geometric spanner with Steiner points
• Stretch factor in a planar Poisson-Delaunay triangulation with a large intensity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q482347)