Constrained empty-rectangle delaunay graphs
Given an arbitrary convex shape C, a set P of points in the plane and a set S of line segments whose endpoints are in P, a constrained generalized Delaunay graph of P with respect to C denoted CDGC(P) is constructed by adding an edge between two points p and q if and only if there exists a homothet of C with p and q on its boundary and no point of P in the interior visible to both p and q. We study the case where the empty convex shape is an arbitrary rectangle and show that the constrained generalized Delaunay graph has spanning ratio at most p2(2l/s + 1), where l and s are the length of the long and short side of the rectangle.
|Conference||27th Canadian Conference on Computational Geometry, CCCG 2015|
Bose, P, De Carufel, J.-L. (Jean-Lou), & Van Renssen, A. (André). (2015). Constrained empty-rectangle delaunay graphs. In Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG 2015 (pp. 57–62).