zbMATH — the first resource for mathematics

Constructing the relative neighborhood graph in 3-dimensional Euclidean space. (English) Zbl 0757.05062
Summary: The relative neighborhood graph for a finite set \(S=\{p_ 1,\dots,p_ N\}\) of points, briefly \(\text{RNG}(S)\), is defined by the following formation rule: \(\overline{p_ ip_ j}\) is an edge in \(\text{RNG}(S)\) if and only if for all \(p_ k\in S-\{p_ i,p_ j\}\), \(\text{dist}(p_ i,p_ j)\leq\max(\text{dist}(p_ i,p_ k),\;\text{dist}(p_ j,p_ k))\). We show that RNG for point sets in \(\mathbb{R}^ 3\) can be constructed in optimal space and \(O(N^ 2\log N)\) time. Also, combinatorial estimates on the size of RNG in \(\mathbb{R}^ 3\) are given.

05C35 Extremal problems in graph theory
Full Text: DOI
[1] Aurenhammer, F., Improved algorithms for discs and balls using power diagrams, J. algorithms, 9, 151-161, (1988) · Zbl 0642.52009
[2] Avis, D.; Erdős, P.; Pach, J., Repeated distances in space, ()
[3] Bollobas, B., Extremal graph theory, (1978), Academic Press London · Zbl 0419.05031
[4] Chung, F.R.K., Sphere-and-point incidence relations in high dimensions with applications to unit distances and furthest-neighbor pairs, Discrete comput. geom., 4, 183-190, (1989) · Zbl 0662.52005
[5] Clarkson, K.L.; Edelsbrunner, H.; Guibas, L.J.; Sharir, M.; Welzl, E., Combinatorial complexity bounds for arrangements of curves and surfaces, Proceedings 29th annual symposium on foundations of computer science, 568-579, (1989)
[6] Edelsbrunner, H.; Seidel, R., Voronoi diagrams and arrangements, Discrete comput. geom., 1, 25-44, (1986) · Zbl 0598.52013
[7] Ichino, M.; Sklansky, J., The relative neighborhood graph for mixed feature variables, Pattern recognition, 18, 161-167, (1985) · Zbl 0563.68070
[8] Imai, H.; Iri, M.; Murota, K., Voronoi diagram in the Laguerre geometry and its applications, SIAM J. comput., 14, 93-105, (1985) · Zbl 0556.68038
[9] Jaromczyk, J.W.; Kowaluk, M., A note on relative neighborhood graphs, (), 233-241, Waterloo
[10] J.W. Jaromczyk, M. Kowaluk and F. Yao, an optimal algorithm for constructing β-skeletons in L_p metric, SIAM J. Comput., to appear.
[11] Katajainen, J., Bucketing and filtering in computational geometry, ()
[12] Kedem, K.; Livne, R.; Pach, J.; Sharir, M., On the union of Jordan region and collision-free translational motion amidst polygonal obstacles, Discrete comput. geom., 1, 59-72, (1986) · Zbl 0594.52004
[13] Kirpatrick, D.G.; Radke, J.D., A framework for computational morphology, (), 217-248
[14] Lankford, P.M., Regionalization: theory and alternative algorithms, Geogr. anal., 1, 196-212, (1969)
[15] Lee, D.T., Relative neighborhood graphs in the L1-metric, Pattern recognition, 18, 327-332, (1985)
[16] O’Rourke, J., Computing the relative neighborhood graph in the L1 and L∞ metrics, Pattern recognition, 8, 45-55, (1982)
[17] Supowit, K.J., The relative neighborhood graph, with an application to minimum spanning trees, J. ACM, 30, 428-448, (1983) · Zbl 0625.68047
[18] Toussaint, G.T., The relative neighborhood graph of a finite planar set, Pattern recognition, 12, 261-268, (1980) · Zbl 0437.05050
[19] Toussaint, G.T., Proceedings 5th International Conference on Pattern Recognition, Miami Beach, Pattern recognition and geometric complexity, 1-24, (1980)
[20] Yao, A.C.-C., On constructing minimum spanning trees in k-dimensional spaces and related problems, SIAM J. discrete math., 11, 721-736, (1982) · Zbl 0492.68050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.