Paper detail

Degree Four Plane Spanners: Simpler and Better

Let ${\cal P}$ be a set of $n$ points embedded in the plane, and let ${\cal C}$ be the complete Euclidean graph whose point-set is ${\cal P}$. Each edge in ${\cal C}$ between two points $p, q$ is realized as the line segment $[pq]$, and is assigned a weight equal to the Euclidean distance $|pq|$. In this paper, we show how to construct in $O(n\lg{n})$ time a plane spanner of ${\cal C}$ of maximum degree at most 4 and stretch factor at most 20. This improves a long sequence of results on the construction of plane spanners of ${\cal C}$. Our result matches the smallest known upper bound of 4 by Bonichon et al. on the maximum degree of plane spanners of ${\cal C}$, while significantly improving their stretch factor upper bound from 156.82 to 20. The construction of our spanner is based on Delaunay triangulations defined with respect to the equilateral-triangle distance, and uses a different approach than that used by Bonichon et al. Our approach leads to a simple and intuitive construction of a well-structured spanner, and reveals useful structural properties of the Delaunay triangulations defined with respect to the equilateral-triangle distance. The structure of the constructed spanner implies that when ${\cal P}$ is in convex position, the maximum degree of this spanner is at most 3. Combining the above degree upper bound with the fact that 3 is a lower bound on the maximum degree of any plane spanner of ${\cal C}$ when the point-set ${\cal P}$ is in convex position, the results in this paper give a tight bound of 3 on the maximum degree of plane spanners of ${\cal C}$ for point-sets in convex position.