Towards plane spanners of degree 3

Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, Anil Maheshwari, Michiel Smid

Abstract


Let $S$ be a finite set of points in the plane. In this paper we consider the problem of computing plane spanners of degree at most three for $S$.

  1. If $S$ is in convex position, then we present an algorithm that constructs a plane $\frac{3+4\pi}{3}$-spanner for $S$ whose vertex degree is at most 3. 
  2. If $S$ is the vertex set of a non-uniform rectangular lattice, then we present an algorithm that constructs a plane $3\sqrt{2}$-spanner for $S$ whose vertex degree is at most 3. 
  3. If $S$ is in general position, then we show how to compute plane degree-3 spanners for $S$ with a linear number of Steiner points.

Full Text:

PDF


DOI: http://dx.doi.org/10.20382/jocg.v8i1a2

ISSN: 1920-180X