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.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-319-48517-1_25
Series Advances in Intelligent Systems and Computing
Citation
Bose, P, De Carufel, J.-L. (Jean-Lou), & van Renssen, A. (André). (2017). Constrained generalized Delaunay graphs are plane spanners. In Advances in Intelligent Systems and Computing. doi:10.1007/978-3-319-48517-1_25