Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The relative neighborhood graph (RNG) of a set S of n points in R is a graph (S, E), where (p, q) &egr; E if and only if there is no point z &egr; S such that max {d(p, z), d(q,z)} < d(p,q). We show that in R , RNG(S) has O(n4/3) edges. We present a randomized algorithm that constructs RNG(S) in expected time O(n3/2+&egr;) assuming that the points of S are in general position. If the points of S are arbitrary, the expected running time is O(n7/4+&egr;). These algorithms can be made deterministic without affecting their asymptotic running time.

REFERENCES

• 1: Pankaj K. Agarwal , Herbert Edelsbrunner , Otfried Schwarzkopf , Emo Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Proceedings of the sixth annual symposium on Computational geometry, p.203-210, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98567]
• 2: P. Agarwal and J. Matou~ek. Ray shooting and parametric search. Manuscript, 1991.
• 3: K P Agarwal , Jiri Matousek , Subhash Suri, Farthest Neighbors, Maximum Spanning Trees and Related Problems in Higher Dimensions, Duke University, Durham, NC, 1991
• 4: M. Chang, C. Tang and R. Lee, Solving the Euclidean bottleneck matching problem by k-relative neighborhood graph, Algorithmica, to appear.
• 5: Bernard Chazelle , Micha Sharir , Emo Welzl, Quasi-optimal upper bounds for simplex range searching and new zone theorems, Proceedings of the sixth annual symposium on Computational geometry, p.23-33, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98532]
• 6: Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM Journal on Computing, v.17 n.4, p.830-847, August 1988 [doi>10.1137/0217052]
• 7: K. Clarkson. New applications of random sampling in computational geometry, Discrete and Computational Geometry 2 (1987), 195-222.
• 8: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 9: Kenneth L. Clarkson , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete & Computational Geometry, v.5 n.2, p.99-160, 1990 [doi>10.1007/BF02187783]
• 10: Herbert Edelsbrunner , Micha Sharir, A hypercube incidence problem with applications to counting distances, Proceedings of the international symposium on Algorithms, p.419-428, August 1990, Tokyo, Japan
• 11: M. Ichino and J. Sklansky. The relative neighborhood graph for mixed feature variables.Pattern Recognition 18 (1985), 161-167.
• 12: J. W. Jaromczyk , M. Kowaluk, A note on relative neighborhood graphs, Proceedings of the third annual symposium on Computational geometry, p.233-241, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41983]
• 13: Jerzy W. Jaromczyk , Miroslław Kowaluk, Constructing the relative neighborhood graph in 3-dimensional Euclidean space, Discrete Applied Mathematics, v.31 n.2, p.181-191, 1991 [doi>10.1016/0166-218X(91)90069-9]
• 14: J. Jarmoczyk, M. Kowaluk and F. Yao. An optimal algorithm for constructing /3-skeltons in Lp metric. SIAM J. Computing, to appear.
• 15: Jyrki Katajaien, The region approach for computing relative neighborhood graphs in the Lp metric, Computing, v.40 n.2, p.147-161, May 1988 [doi>10.1007/BF02247943]
• 16: J Katajainen , O Nevalainen, Computing relative neighbourhood graphs in the plane, Pattern Recognition, v.19 n.3, p.221-228, 1986 [doi>10.1016/0031-3203(86)90012-9]
• 17: Jiří Matoušek, Approximations and optimal geometric divide-and-conquer, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.505-511, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103470]
• 18: J. O'Rourke. Computing the relative neighborhood graph in L1 and Loo metrics. Pattern Recognition 14 (1 so2), 45-55.
• 19: Tung-Hsin Su , Ruei-Chuan Chang, Computing the constrained relative neighborhood graphs and constrained Gabriel graphs in Euclidean plane, Pattern Recognition, v.24 n.3, p.221-230, 1991 [doi>10.1016/0031-3203(91)90064-C]
• 20: Tung-Hsin Su , Ruei-Chuan Chang, Computing the k-relative neighborhood graphs in Euclidean plane, Pattern Recognition, v.24 n.3, p.231-239, 1991 [doi>10.1016/0031-3203(91)90065-D]
• 21: Kenneth J. Supowit, The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees, Journal of the ACM (JACM), v.30 n.3, p.428-448, July 1983 [doi>10.1145/2402.322386]
• 22: G. Toussaint. The relative neighborhood graph of a finite planar set. Pattern Recognition 12 (1980), 261- 268.
• 23: G. Toussaint. Pattern recognition and geometric complexity. Proc. 5ta International Conference on Pattern Recognition, 1980, pp. 1-24.
• 24: R. Urquhart. Some properties of the planar Euclidean relative neighborhood graph. Pattern Recognition Letters 1 (1983), 317-322.
• 25: A. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems, SIAM J. Computing 11 (1982), 721-736.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory, Verification