The relative neighborhood graph, with an application to minimum spanning trees. (English) Zbl 0625.68047

Supowit, Kenneth J.

J. Assoc. Comput. Mach. 30, 428-448 (1983).

The relative neighborhood graph (RNG) of a set V of points in Euclidean space is the graph (V,E), where (p,q)\(\in E\) iff there is no point \(z\in V\) such that \(d(p,z)<d(p,q)\) and \(d(q,z)<d(p,q)\). It is shown that (1) the RNG of n points in the plane can be found in O(n log n) time, which is optimal to within a multiplicative constant. (2) The RNG, as well as the minimum spanning tree, of the vertices of a convex, n-vertex polygon can be found in O(n) time, given the vertices in sorted clockwise order. (3) Under the assumption that no three input points form an isosceles triangle, the RNG of n points in r-dimensional space can be found in \(O(n^ 2)\) time for fixed \(r\geq 3\).

MSC:

68R10

Graph theory (including graph drawing) in computer science

Keywords:

graph algorithms; relative neighborhood graph; minimum spanning tree