×
Katajainen, Jyrki; Nevalainen, Olli; Teuhola, Jukka

A linear expected-time algorithm for computing planar relative neighbourhood graphs. (English) Zbl 0653.68034

Inf. Process. Lett. 25, 77-86 (1987).
A new algorithm for computing the relative neighbourhood graph (RNG) of a planar point set is given. The expected running time of the algorithm is linear for a point set in a unit square when the points have been generated by a homogeneous planar Poisson point process. The worst-case running time is quadratic on the number of the points. The algorithm proceeds in two steps. First, a supergraph of the RNG is constructed with the aid of a cell organization of the points. Here, a point is connected by an edge to some of its nearest neighbours in eight regions around the point. The nearest region neighbours are chosen in a special way to minimize the costs. Second, extra edges are pruned from the graph by a simple scan.

Cited in 3 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
52A37 Other problems of combinatorial convexity

Keywords:

Voronoi diagram; cell technique; region approach; computational geometry; relative neighbourhood graph; planar point set
PDF BibTeX XML Cite
\textit{J. Katajainen} et al., Inf. Process. Lett. 25, 77--86 (1987; Zbl 0653.68034)
Full Text: DOI

References:

[1] Bentley, J. L.; Weide, B. W.; Yao, A. C., Optimal expected-time algorithms for closest point problems, ACM Trans. Math. Software, 6, 563-580 (1980) · Zbl 0441.68077
[2] Gabow, H. N.; Bentley, J. L.; Tarjan, R. E., Scaling and related techniques for geometric problems, (Proc. 16th Ann. ACM Symp. on Theory of Computing. Proc. 16th Ann. ACM Symp. on Theory of Computing, Washington, D.C. (1984)), 135-143
[3] Katajainen, J., The region approach for computing relative neighbourhood graphs in the \(L_p\) metric, (Rept. B38 (1986), Dept. of Computer Science, Univ. of Turku: Dept. of Computer Science, Univ. of Turku Finland) · Zbl 0628.68055
[4] Katajainen, J.; Nevalainen, O., Three programs for computing the relative neighbourhood graphs in the plane, (Rept. D29 (1985), Dept. of Computer Science, Univ. of Turku: Dept. of Computer Science, Univ. of Turku Finland) · Zbl 0602.68089
[5] Katajainen, J.; Nevalainen, O., Computing relative neighbourhood graphs in the plane, Pattern Recognition, 19, 221-228 (1986) · Zbl 0602.68089
[6] Maus, A., Delanay triangulation and the convex hull of \(n\) points in expected linear time, BIT, 24, 151-163 (1984) · Zbl 0548.68068
[7] Rohatgi, V. K., An Introduction to Probability Theory and Mathematical Statistics (1976), Wiley: Wiley New York · Zbl 0354.62001
[8] Shamos, M. I., Computational geometry, (Ph.D. Thesis (1978), Dept. of Computer Science, Yale Univ: Dept. of Computer Science, Yale Univ New Haven, CT) · Zbl 0759.68037
[9] Supowit, K. J., The relative neighbourhood graph with an application to minimum spanning trees, J. ACM, 30, 3, 428-448 (1983) · Zbl 0625.68047
[10] Toussaint, G. T., The relative neighbourhood graph of a finite set, Pattern Recognition, 12, 261-268 (1980) · Zbl 0437.05050
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.