License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2016.45
URN: urn:nbn:de:0030-drops-59376
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5937/
Go to the corresponding LIPIcs Volume Portal

Kanj, Iyad ; Perkovic, Ljubomir ; Türkoglu, Duru

Degree Four Plane Spanners: Simpler and Better

pdf-format:
LIPIcs-SoCG-2016-45.pdf (0.5 MB)

Abstract

Let P be a set of n points embedded in the plane, and let C be the complete Euclidean graph whose point-set 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 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.

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:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{S{\'a}ndor Fekete and Anna Lubiw},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5937},
  URN =		{urn:nbn:de:0030-drops-59376},
  doi =		{10.4230/LIPIcs.SoCG.2016.45},
  annote =	{Keywords: Nonnumerical Algorithms and Problems,Computational Geometry and Object Modeling}
}

Keywords: Nonnumerical Algorithms and Problems,Computational Geometry and Object Modeling
Collection: 32nd International Symposium on Computational Geometry (SoCG 2016)
Issue Date: 2016
Date of publication: 10.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI