Kanj, Iyad ;
Perkovic, Ljubomir ;
Türkoglu, Duru
Degree Four Plane Spanners: Simpler and Better
Abstract
Let P be a set of n points embedded in the plane, and let C be the complete Euclidean graph whose pointset is P. Each edge in 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(nlg{n}) time a plane spanner of C of maximum degree at most 4 and of stretch factor at most 20. This improves a long sequence of results on the construction of bounded degree plane spanners of C. Our result matches the smallest known upper bound of 4 by Bonichon et al. on the maximum degree 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 equilateraltriangle distance, and uses a different approach than that used by Bonichon et al. Our approach leads to a simple and intuitive construction of a wellstructured spanner, and reveals useful structural properties of the Delaunay triangulations defined with respect to the equilateraltriangle distance.
BibTeX  Entry
@InProceedings{kanj_et_al:LIPIcs:2016:5937,
author = {Iyad Kanj and Ljubomir Perkovic and Duru T{\"u}rkoglu},
title = {{Degree Four Plane Spanners: Simpler and Better}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {45:145:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770095},
ISSN = {18688969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5937},
URN = {urn:nbn:de:0030drops59376},
doi = {10.4230/LIPIcs.SoCG.2016.45},
annote = {Keywords: Nonnumerical Algorithms and Problems,Computational Geometry and Object Modeling}
}
10.06.2016
Keywords: 

Nonnumerical Algorithms and Problems,Computational Geometry and Object Modeling 
Seminar: 

32nd International Symposium on Computational Geometry (SoCG 2016)

Issue date: 

2016 
Date of publication: 

10.06.2016 