# 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.

##### MSC:
 68Q25 Analysis of algorithms and problem complexity 68R10 Graph theory (including graph drawing) in computer science 52A37 Other problems of combinatorial convexity
Full Text:
##### References:
  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  Gabow, H.N.; Bentley, J.L.; Tarjan, R.E., Scaling and related techniques for geometric problems, (), 135-143  Katajainen, J., The region approach for computing relative neighbourhood graphs in the L_p metric, () · Zbl 0628.68055  Katajainen, J.; Nevalainen, O., Three programs for computing the relative neighbourhood graphs in the plane, () · Zbl 0602.68089  Katajainen, J.; Nevalainen, O., Computing relative neighbourhood graphs in the plane, Pattern recognition, 19, 221-228, (1986) · Zbl 0602.68089  Maus, A., Delanay triangulation and the convex hull of n points in expected linear time, Bit, 24, 151-163, (1984) · Zbl 0548.68068  Rohatgi, V.K., An introduction to probability theory and mathematical statistics, (1976), Wiley New York · Zbl 0354.62001  Shamos, M.I., Computational geometry, () · Zbl 0759.68037  Supowit, K.J., The relative neighbourhood graph with an application to minimum spanning trees, J. ACM, 30, 3, 428-448, (1983) · Zbl 0625.68047  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.