A linear expected-time algorithm for computing planar relative neighbourhood graphs

DOI10.1016/0020-0190(87)90225-0MaRDI QIDQ1108002zbMATH OpenOpenAlexFDO

Authors Jyrki Katajainen, Jukka Teuhola, Olli S. Nevalainen

Publication date 1987

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(87)90225-0

zbMATH Keywords

cell techniquecomputational geometryplanar point setregion approachrelative neighbourhood graphVoronoi diagram

Mathematics Subject Classification ID

Other problems of combinatorial convexity (52A37) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

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.

Recommendations

• Computing relative neighbourhood graphs in the plane
• An almost naive algorithm for finding relative neighbourhood graphs in L_p metrics
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• Relative neighborhood graphs in three dimensions
• A linear-time construction of the relative neighborhood graph from the Delaunay triangulation

Cites work

• Computing relative neighbourhood graphs in the plane
• Delaunay triangulation and the convex hull of n points in expected linear time
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3551675 (Why is no real title available?)
• Optimal Expected-Time Algorithms for Closest Point Problems
• The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• The relative neighbourhood graph of a finite planar set

Cited in

(6)

• Computing relative neighbourhood graphs in the plane
• The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric
• A linear-time construction of the relative neighborhood graph from the Delaunay triangulation
• An almost naive algorithm for finding relative neighbourhood graphs in L_p metrics
• scientific article; zbMATH DE number 4080989 (Why is no real title available?)
• On constructing the relative neighborhood graphs in Euclidean k- dimensional spaces

This page was built for publication: A linear expected-time algorithm for computing planar relative neighbourhood graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108002)