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

DOI10.1016/J.COMGEO.2014.10.005MaRDI QIDQ482347zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

Delaunay triangulation\(L_p\)-metricgeometric spannerstretch factor

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(17)

• Stretch factor in a planar Poisson-Delaunay triangulation with a large intensity
• 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
• Delaunay simplices in diagonally distorted lattices
• 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}\)
• Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
• On the stretch factor of Delaunay triangulations of points in convex position
• Improved routing on the Delaunay triangulation
• The stretch factor of hexagon-Delaunay triangulations
• Emanation graph: a plane geometric spanner with Steiner points

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)