Constrained Empty-Rectangle Delaunay Graphs.
Prosenjit K. Bose, Jean-Lou De Carufel, André van Renssen · 2015
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 2·(2l/s+ 1), where l and s are the length of the long and short side of the rectangle. 1