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

DOI10.1016/0020-0190(87)90225-0zbMATH Open0653.68034OpenAlexW1993153243MaRDI QIDQ1108002FDOQ1108002

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

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

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)

Cites Work

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

Cited In (5)

• Title not available (Why is that?)
• 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)