×

zbMATH — the first resource for mathematics

Computing relative neighbourhood graphs in the plane. (English) Zbl 0602.68089
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

MSC:
68T10 Pattern recognition, speech recognition
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
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, ()
[6] Katajainen, J.; Nevalainen, O., Three programs for computing the relative neighbourhood graphs in the plane, () · 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
[8] T. Leipälä, Private communication, 4 March 1985.
[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 L1 and L∞ metrics, Pattern recognition, 15, 189-192, (1982) · Zbl 0486.68063
[14] Santalo, L.A., Integral geometry and geometric probability, (1976), Addison-Wesley Reading, MA · Zbl 0063.06708
[15] Shamos, M.I., Computational geometry, () · 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, ()
[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, (), 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, (), 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, ()
[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.