On Generalized Diamond Spanners

Given a set P of points in the plane and a set L of non-crossing line segments whose endpoints are in P, a constrained plane geometric graph is a plane graph whose vertex set is P and whose edge set contains L. An edge e has the α-visible diamond property if one of the two isosceles triangles with base e and base angle α does not contain any points of P visible to both endpoints of e. A constrained plane geometric graph has the d-good polygon property provided that for every pair x, y of visible vertices on a face f, the shorter of the two paths from x to y around the boundary has length at most d · |xy|. If a constrained plane geometric graph has the α-visible diamond property for each of its edges and the d-good polygon property, we show it is a 8d(π−α)2 α2 sin2-spanner of the visibility graph of P and L. This is a generalization (α/4) of the result in Das and Joseph [3] to the constrained setting as well as a slight improvement 8dπ on their spanning ratio of 2 α2 sin2. We then show that several well-known constrained tri-(α/4) angulations (namely the constrained Delaunay triangulation, constrained greedy triangulation and constrained minimum weight triangulation) have the α-visible diamond property for some constant α. In particular, we show that the greedy triangulation has the π/6-visible diamond property, which is an improvement over previous results.