Browsing by Author "SU, TH"

Now showing 1 - 5 of 5

COMPUTING THE CONSTRAINED RELATIVE NEIGHBORHOOD GRAPHS AND CONSTRAINED GABRIEL GRAPHS IN EUCLIDEAN PLANE
(1991)
SU, TH
;
CHANG, RC
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
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 THETA-(n log n) time.
COMPUTING THE K-RELATIVE NEIGHBORHOOD GRAPHS IN EUCLIDEAN PLANE
(1991)
SU, TH
;
CHANG, RC
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
In this paper, we will propose an O(n5/3log n) algorithm to construct the k-relative neighborhood graph of a n points set in Euclidean plane, for fixed k. Based on this result, the Euclidean bottleneck matching problem can also be solved in the same time complexity. The k-relative neighborhood graph is a generalization of the relative neighborhood graph.
ON CONSTRUCTING THE RELATIVE NEIGHBORHOOD GRAPHS IN EUCLIDEAN K-DIMENSIONAL SPACES
(1991)
SU, TH
;
CHANG, RC
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
In this paper, a new algorithm for constructing the relative neighborhood graph(RNG) of an n points set in Euclidean k-dimensional space is presented, for fixed k greater-than-or-equal-to 3. The worst case running time of the algorithm is O(n2-a(k)(log n)1-a(k)), for a(k) = 2-(k+1), which is under the assumption that no three input points form an isosceles triangle. Previous algorithms need O(n2) time. Our algorithm proceeds in two phases. First, a supergraph of RNG with O(n) edges is constructed and then those edges which do not belong to RNG are eliminated.
THE K-GABRIEL GRAPHS AND THEIR APPLICATIONS
(1990-01-01)
SU, TH
;
CHANG, RC
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
THE K-GABRIEL GRAPHS AND THEIR APPLICATIONS
(1990)
SU, TH
;
CHANG, RC
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering