Degree four plane spanners: simpler and better

DOI10.20382/JOCG.V8I2A2zbMATH Open1405.68424arXiv1603.03818OpenAlexW2964200445MaRDI QIDQ2970474FDOQ2970474

Authors: Ljubomir Perković, Duru Türkoğlu, Iyad Kanj 

Publication date: 30 March 2017

Abstract: Let $calP$ be a set of $n$ points embedded in the plane, and let $calC$ be the complete Euclidean graph whose point-set is $calP$. Each edge in $calC$ 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(nlgn)$ time a plane spanner of $calC$ 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 $calC$. Our result matches the smallest known upper bound of 4 by Bonichon et al. on the maximum degree of plane spanners of $calC$, 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 $calP$ 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 $calC$ when the point-set $calP$ is in convex position, the results in this paper give a tight bound of 3 on the maximum degree of plane spanners of $calC$ for point-sets in convex position.

Full work available at URL: https://arxiv.org/abs/1603.03818

Recommendations

• Degree four plane spanners: simpler and better
• There are plane spanners of degree 4 and moderate stretch factor
• There are Plane Spanners of Maximum Degree 4
• Plane Spanners of Maximum Degree Six
• scientific article; zbMATH DE number 1947396

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (18)

• There are plane spanners of degree 4 and moderate stretch factor
• Bounded-degree spanners in the presence of polygonal obstacle
• Towards plane spanners of degree 3
• Bounded-degree plane geometric spanners in practice
• A note on optimal degree-three spanners of the square lattice
• On path-greedy geometric spanners
• New Doubling Spanners: Better and Simpler
• Towards plane spanners of degree 3
• Plane Spanners of Maximum Degree Six
• Diamond Triangulations Contain Spanners of Bounded Degree
• A plane 1.88-spanner for points in convex position
• Lower bounds on the dilation of plane spanners
• Local routing in sparse and lightweight geometric graphs
• New Doubling Spanners: Better and Simpler
• On bounded degree plane strong geometric spanners
• Emanation graph: a plane geometric spanner with Steiner points
• Degree four plane spanners: simpler and better
• Lower bounds on the dilation of plane spanners

This page was built for publication: Degree four plane spanners: simpler and better

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2970474)