Computing the constrained relative neighborhood graphs and constrained gabriel graphs in Euclidean plane

摘要

The original relative neighborhood graph (RNG) and Gabriel graph (GG) were defined on a vertices set in the plane. In this paper, we will extend this domain to a planar straight-line graph, and call this type of RNG and GG the constrained relative neighborhood graph (CRNG) and the constrained Gabriel graph (CGG) respectively. Given a planar straight-line graph G in the plane, the edges of the CRNG of G(CRNG(G)) satisfy the following two properties: (1) All of the edges in G (called prespecified edges) are included in the CRNG(G) and the remaining edges do not properly intersect with them; (2) If a non-prespecified edge (p,q) belongs to the CRNG(G) then either there does not exist a vertex z such that d(p,z) < d(p,q) and d(q,z) < d(p,q), or if z satisfies the above condition then z must be invisible by p or q (i.e. if you draw the line segments from z to p and q, then at least one of the lines segments crosses a prespecified edge of G). The constrained Gabriel graph is defined similarly. The CRNG and CGG are the extensions of RNG and GG respectively for which one can specify in advance some special or important edges which must be included in the outcome graph. These variants of RNG and GG provide a new application for the original RNG and GG. In this paper, we will show that both CRNG and CGG are subgraphs of the constrained Delaunay triangulation, and propose two optimal algorithms to construct them in ϑ(n log n) time.