2026-07-23T01:18:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6788 2024-03-06T10:38:53Z ddc:004 open_access

Towards Plane Spanners of Degree 3 Biniaz, Ahmad Bose, Prosenjit De Carufel, Jean-Lou Gavoille, Cyril Maheshwari, Anil Smid, Michiel plane spanners degree-3 spanners convex position non-uniform lattice Let S be a finite set of points in the plane that are in convex position. We present an algorithm that constructs a plane frac{3+4 pi}{3}-spanner of S whose vertex degree is at most 3. Let Lambda be the vertex set of a finite non-uniform rectangular lattice in the plane. We present an algorithm that constructs a plane 3 sqrt{2}-spanner for Lambda whose vertex degree is at most 3. For points that are in the plane and in general position, we show how to compute plane degree-3 spanners with a linear number of Steiner points. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ahmad Biniaz and Prosenjit Bose and Jean-Lou De Carufel and Cyril Gavoille and Anil Maheshwari and Michiel Smid 2016 Is Part Of LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2016.19 urn:nbn:de:0030-drops-67887 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.19 eng https://creativecommons.org/licenses/by/3.0/legalcode