On the stretch factor of Delaunay triangulations of points in convex position

DOI10.1016/j.comgeo.2010.09.007zbMath1217.65046OpenAlexW2038433986MaRDI QIDQ621926

Iyad A. Kanj, Ge Xia, Shiliang Cui

Publication date: 31 January 2011

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

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

zbMATH Keywords

convex positiongeometric graphDelaunay triangulationEuclidean distamcestretch factor/dilation

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Distance in graphs (05C12) Other problems of combinatorial convexity (52A37) Convex sets in (2) dimensions (including convex curves) (52A10)

Related Items

Linear-size planar Manhattan network for convex point sets ⋮ Competitive Online Routing on Delaunay Triangulations ⋮ On plane geometric spanners: a survey and open problems ⋮ Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\) ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Improved stretch factor of Delaunay triangulations of points in convex position

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Delaunay graphs are almost as good as complete graphs
• Constructing plane spanners of bounded degree and low weight
• Classes of graphs which approximate the complete Euclidean graph
• There are planar graphs almost as good as the complete graph
• On Spanners and Lightweight Spanners of Geometric Graphs
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• Geometric Spanner Networks

This page was built for publication: On the stretch factor of Delaunay triangulations of points in convex position