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

computational geometryVoronoi diagramplanar 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)

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

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

Cited in

(5)

• scientific article; zbMATH DE number 4080989 (Why is no real title available?)
• On constructing the relative neighborhood graphs in Euclidean k- dimensional spaces
• Computing relative neighbourhood graphs in the plane
• 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

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)