On the Spanning Ratio of the Greedy Triangulation for Convex Point Sets
2026-08-10 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors study a method for connecting points on a flat surface called greedy triangulation, which adds edges in order of increasing length without crossing. They focus on points arranged in a convex shape and improve the known upper limit on how much longer paths in this network can be compared to the direct distance between points. Their new proof shows that any path between two points in the greedy triangulation is less than about 18 times the direct distance, much smaller than the previous upper bound. This means the network is an 18-spanner, efficiently approximating direct connections between points.
greedy triangulationplanar point setconvex positionspanning ratiospannerEuclidean distancegeometric graphpath lengthnon-crossing segmentsconvex hull
Authors
Prosenjit Bose, Jean Lou de Carufel, Anil Maheshwari, Bobby Miraftab, Michiel Smid, Leonidas Theocharous
Abstract
The greedy triangulation of a finite planar point set is obtained by considering all segments in nondecreasing order of length and inserting each segment that does not cross an earlier one. Its spanning ratio is known to be bounded by a universal constant, but the standard bound obtained from the diamond and good-polygon properties is about $11739.1$. We prove a substantially smaller bound for points in convex position. In particular, for every finite point set $P\subset\mathbb{R}^2$ in convex position and every pair $u,v\in P$, the greedy triangulation contains a $u$--$v$ path of length at most $κ|uv|$, where $κ<17.814$. Thus, the greedy triangulation of a convex point set is an $18$-spanner.