zbMATH — the first resource for mathematics

A linear expected-time algorithm for computing planar relative neighbourhood graphs. (English) Zbl 0653.68034
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.

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
52A37 Other problems of combinatorial convexity
Full Text: DOI
[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, (), 135-143
[3] Katajainen, J., The region approach for computing relative neighbourhood graphs in the L_p metric, () · Zbl 0628.68055
[4] Katajainen, J.; Nevalainen, O., Three programs for computing the relative neighbourhood graphs in the plane, () · 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 New York · Zbl 0354.62001
[8] Shamos, M.I., Computational geometry, () · 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.