Document Open Access Logo

Degree Four Plane Spanners: Simpler and Better

Authors Iyad Kanj, Ljubomir Perkovic, Duru Türkoglu

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.45.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Iyad Kanj
Ljubomir Perkovic
Duru Türkoglu

Cite As Get BibTex

Iyad Kanj, Ljubomir Perkovic, and Duru Türkoglu. Degree Four Plane Spanners: Simpler and Better. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.45

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.

Subject Classification

Keywords
  • Nonnumerical Algorithms and Problems,Computational Geometry and Object Modeling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. N. Bonichon, C. Gavoille, N. Hanusse, and D. Ilcinkas. Connections between theta-graphs, delaunay triangulations, and orthogonal surfaces. In Proceedings of the 36th International Workshop on Graph Theoretic Concepts in Computer Science, volume 6410 of Lecture Notes in Computer Science, pages 266-278, 2010. Google Scholar
  2. N. Bonichon, C. Gavoille, N. Hanusse, and L. Perković. Plane spanners of maximum degree six. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), volume 6198 of Lecture Notes in Computer Science, pages 19-30. Springer, 2010. Google Scholar
  3. N. Bonichon, C. Gavoille, N. Hanusse, and L. Perković. The stretch factor of L₁- and L_∞-Delaunay triangulations. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA), volume 7501 of Lecture Notes in Computer Science, pages 205-216. Springer, 2012. Google Scholar
  4. N. Bonichon, I. Kanj, L. Perkovic, and G. Xia. There are plane spanners of degree 4 and moderate stretch factor. Discrete & Computational Geometry, 53(3):514-546, 2015. Google Scholar
  5. P. Bose, P. Carmi, and L. Chaitman-Yerushalmi. On bounded degree plane strong geometric spanners. J. Discrete Algorithms, 15:16-31, 2012. Google Scholar
  6. P. Bose, P. Carmi, S. Collette, and M. Smid. On the stretch factor of convex delaunay graphs. Journal of Computational Geometry, 1(1):41-56, 2010. Google Scholar
  7. P. Bose, J. Gudmundsson, and M. Smid. Constructing plane spanners of bounded degree and low weight. Algorithmica, 42(3-4):249-264, 2005. Google Scholar
  8. P. Bose, P. Morin, I. Stojmenović, and J. Urrutia. Routing with guaranteed delivery in ad hoc wireless networks. Wireless Networks, 7(6):609-616, 2001. Google Scholar
  9. P. Bose, M. Smid, and D. Xu. Delaunay and diamond triangulations contain spanners of bounded degree. International Journal of Computational Geometry and Applications, 19(2):119-140, 2009. Google Scholar
  10. L. P. Chew. There is a planar graph almost as good as the complete graph. In Proceedings of the Second Annual Symposium on Computational Geometry (SoCG), pages 169-177, 1986. Google Scholar
  11. L. P. Chew. There are planar graphs almost as good as the complete graph. Journal of Computer and System Sciences, 39(2):205-219, 1989. Google Scholar
  12. G. Das and P.J. Heffernan. Constructing degree-3 spanners with other sparseness properties. Int. J. Found. Comput. Sci., 7(2):121-136, 1996. Google Scholar
  13. D. Dobkin, S. Friedman, and K. Supowit. Delaunay graphs are almost as good as complete graphs. Discrete &Computational Geometry, 5(4):399-407, December 1990. URL: http://dx.doi.org/10.1007/BF02187801.
  14. I. Kanj and L. Perković. On geometric spanners of Euclidean and unit disk graphs. In In Proceedings of the 25^th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume hal-00231084, pages 409-420. HAL, 2008. Google Scholar
  15. I. Kanj, L. Perković, and D. Türkoğlu. Degree Four Plane Spanners: Simpler and Better. CoRR, abs/1603.03818, 2016. URL: http://arxiv.org/abs/1603.03818.
  16. J. M. Keil and C. A. Gutwin. Classes of graphs which approximate the complete Euclidean graph. Discrete &Computational Geometry, 7(1):13-28, 1992. Google Scholar
  17. X.-Y. Li and Y. Wang. Efficient construction of low weight bounded degree planar spanner. International Journal of Computational Geometry and Applications, 14(1-2):69-84, 2004. Google Scholar
  18. J. Salowe. Euclidean spanner graphs with degree four. Discrete Applied Mathematics, 54(1):55-66, 1994. Google Scholar
  19. Y. Wang and Xiang-Yang L. Localized construction of bounded degree and planar spanner for wireless ad hoc networks. Mobile Networks and Applications, 11(2):161-175, 2006. Google Scholar
  20. G. Xia. The stretch factor of the Delaunay triangulation is less than 1.998. SIAM J. Comput., 42(4):1620-1659, 2013. URL: http://dx.doi.org/10.1137/110832458.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact