Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6868402 | Computational Geometry | 2018 | 16 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Prosenjit Bose, Jean-Lou De Carufel, André van Renssen,