×
Katajainen, Jyrki; Nevalainen, Olli

Computing relative neighbourhood graphs in the plane. (English) Zbl 0602.68089

Pattern Recognition 19, 221-228 (1986).
The paper presents two new algorithms for constructing the relative neighborhood graph (RNG) in two-dimensional Euclidean space. The method is to determine a supergraph for RNG which can be thinned efficiently from the extra edges.
Reviewer: N.N.Necula

Cited in 10 Documents

MSC:

68T10 Pattern recognition, speech recognition
68R10 Graph theory (including graph drawing) in computer science

Keywords:

graph algorithms; pattern recognition; nearest neighbour search
PDF BibTeX XML Cite
\textit{J. Katajainen} and \textit{O. Nevalainen}, Pattern Recognition 19, 221--228 (1986; Zbl 0602.68089)
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] Chang, R. C.; Lee, R. C.T., The average performance analysis of a closest-pair algorithm, Int. J. Comput. Math., 16, 125-130 (1984) · Zbl 0547.68045
[3] Chang, R. C.; Lee, R. C.T., On the average length of Delaunay triangulations, BIT, 24, 269-273 (1984) · Zbl 0572.65099
[4] Cheriton, D.; Tarjan, R. E., Finding minimum spanning trees, SIAM J. Comput., 5, 724-742 (1976) · Zbl 0358.90069
[5] Helmiö, A., Delaunayn kolmiointi ja siitä johdettu suhteellisen vierekkäisyyden graafi, (M.Sc. thesis (1985), Department of Computer Science, University of Turku: Department of Computer Science, University of Turku Finland)
[6] Katajainen, J.; Nevalainen, O., Three programs for computing the relative neighbourhood graphs in the plane, (Report D29 (1985), Department of Computer Science, University of Turku: Department of Computer Science, University of Turku Finland) · Zbl 0602.68089
[7] Lee, D. T.; Schachter, B. J., Two algorithms for constructing a Delaunay triangulation, Int. J. Comput. Inf. Sci., 9, 219-242 (1980) · Zbl 0441.68047
[9] Leipälä, T.; Nevalainen, O., On the dynamic nearest neighbour problem, RAIRO Informatique/Comput. Sci., 13, 3-15 (1979) · Zbl 0402.68043
[10] Matula, D. W.; Sokal, R. R., Properties of Gabriel graphs relevant to geographical variation research and clustering of points in the plane, Geogr. Anal., 12, 205-222 (1980)
[11] Maus, A., Delaunay triangulation and the convex hull of \(n\) points in expected linear time, BIT, 24, 151-163 (1984) · Zbl 0548.68068
[12] Miles, R. E., On the homogeneous planar Poisson point process, Math. Biosci., 6, 85-127 (1970) · Zbl 0196.19403
[13] O’Rourke, J., Computing the relative neighbourhood graph in the \(L_1\) and \(L_∞\) metrics, Pattern Recognition, 15, 189-192 (1982) · Zbl 0486.68063
[14] Santalo, L. A., Integral Geometry and Geometric Probability (1976), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0063.06708
[15] Shamos, M. I., Computational geometry, (Ph.D. thesis (1978), Yale University: Yale University New Haven) · Zbl 0759.68037
[16] Supowit, K. J., The relative neighborhood graph, with an application to minimum spanning trees, J. ACM, 30, 428-448 (1983) · Zbl 0625.68047
[17] Tamminen, M., Metric data structures—an overview, (Report HTKK-TKO-A25 (1984), Laboratory of Information Processing Science, Helsinki University of Technology: Laboratory of Information Processing Science, Helsinki University of Technology Finland)
[18] Toussaint, G. T., The relative neighbourhood graph of a finite planar set, Pattern Recognition, 12, 261-268 (1980) · Zbl 0437.05050
[19] Toussaint, G. T., Pattern recognition and geometrical complexity, (Proc. 5th Int. Conf. on Pattern Recognition. Proc. 5th Int. Conf. on Pattern Recognition, Miami Beach (1980)), 1324-1347
[20] Toussaint, G. T., Comment on “Algorithms for computing relative neighbourhood graph”, Electronics Lett., 16, 860-861 (1980)
[21] Toussaint, G. T.; Menard, R., Fast algorithms for computing the planar relative neighborhood graph, (Proc. 5th Symp. on Operations Research. Proc. 5th Symp. on Operations Research, Köln (1980)), 425-428 · Zbl 0467.90028
[22] Urquhart, R. B., Algorithms for computation of relative neighbourhood graph, Electronics Lett., 16, 556-557 (1980)
[23] Weide, B. W., Statistical methods in algorithm design and analysis, (Ph.D. thesis (1978), Carnegie-Mellon University: Carnegie-Mellon University Pittsburgh)
[24] Yao, A. C., On constructing minimum spanning trees in \(k\)-dimensional spaces and related problems, SIAM J. Comput., 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.