We look at generalized Delaunay graphs in the constrained setting by introducing line segments which the edges of the graph are not allowed to cross. Given an arbitrary convex shape C, a constrained Delaunay graph is constructed by adding an edge between two vertices p and q if and only if there exists a homothet of C with p and q on its boundary that does not contain any other vertices visible to p and q. We show that, regardless of the convex shape C used to construct the constrained Delaunay graph, there exists a constant t (that depends on C) such that it is a plane t-spanner of the visibility graph. Furthermore, we reduce the upper bound on the spanning ratio for the special case where the empty convex shape is an arbitrary rectangle to 2⋅(2l/s+1), where l and s are the length of the long and short side of the rectangle.

, ,
Computational Geometry
School of Computer Science

Bose, P, De Carufel, J.-L. (Jean-Lou), & van Renssen, A. (André). (2018). Constrained generalized Delaunay are plane spanners. Computational Geometry. doi:10.1016/j.comgeo.2018.06.006