Towards plane spanners of degree 3
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.
|Keywords||Convex position, Degree-3 spanners, Non-uniform lattice, Plane spanners|
|Conference||27th International Symposium on Algorithms and Computation, ISAAC 2016|
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