Experimental improvements on the plane spanners on points in convex position

A geometric graph is called a t-spanner, for $t\geq 1$, if the shortest path between any two vertices is at most t times their Euclidean distance.In this paper, we study the construction of planar geometric t-spanners for point sets in convex position. We consider two existing algorithms and propose a new algorithm for this problem. We theoretically and experimentally compare these three approaches in terms of stretch factor, maximum vertex degree, graph diameter, total weight, and running time. Extensive experiments were conducted on more than 7,000 convex point sets of varying sizes and shapes. The results show that although the proposed algorithm has a higher running time than the existing algorithms, it produces planar t-spanners with significantly smaller stretch factors---bounded above by $\sqrt{3}$---as well as smaller maximum vertex degrees and graph diameters. Furthermore, the proposed algorithm yields lighter spanners for fat convex point sets, especially for large input sizes, while achieving comparable performance on skinny convex configurations. To the best of our knowledge, the resulting spanners achieve some of the smallest known stretch factors, with a proven upper bound of at most $1.88$.