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

DOI10.1016/0020-0190(87)90225-0zbMath0653.68034OpenAlexW1993153243MaRDI QIDQ1108002

Jukka Teuhola, Jyrki Katajainen, 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

Voronoi diagramcomputational geometryplanar point setrelative neighbourhood graphregion approachcell technique

Mathematics Subject Classification ID

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

Related Items (3)

The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric ⋮ An almost naive algorithm for finding relative neighbourhood graphs in $L_p$ metrics ⋮ On constructing the relative neighborhood graphs in Euclidean k- dimensional spaces

Cites Work

• Delaunay triangulation and the convex hull of n points in expected linear time
• Computing relative neighbourhood graphs in the plane
• The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric
• The relative neighbourhood graph of a finite planar set
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• Optimal Expected-Time Algorithms for Closest Point Problems
• Unnamed Item
• Unnamed Item

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