2016-12-01
Towards plane spanners of degree 3
Publication
Publication
Presented at the
27th International Symposium on Algorithms and Computation, ISAAC 2016 (December 2016), Sydney
Let S be a finite set of points in the plane that are in convex position. We present an algorithm that constructs a plane 3+4π/3 -spanner of S whose vertex degree is at most 3. Let Λ be the vertex set of a finite non-uniform rectangular lattice in the plane. We present an algorithm that constructs a plane 3√2-spanner for Ë 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.
| Additional Metadata | |
|---|---|
| Keywords | Convex position, Degree-3 spanners, Non-uniform lattice, Plane spanners |
| Persistent URL | dx.doi.org/10.4230/LIPIcs.ISAAC.2016.19 |
| Conference | 27th International Symposium on Algorithms and Computation, ISAAC 2016 |
| Citation |
Biniaz, A. (Ahmad), Bose, P, De Carufel, J.-L. (Jean-Lou), Gavoille, C. (Cyril), Maheshwari, A, & Smid, M. (2016). Towards plane spanners of degree 3. In Leibniz International Proceedings in Informatics, LIPIcs (pp. 19.1–19.14). doi:10.4230/LIPIcs.ISAAC.2016.19
|