A linear-time construction of the relative neighborhood graph from the Delaunay triangulation

DOI10.1016/0925-7721(94)90018-3zbMath0813.68161OpenAlexW2067049088MaRDI QIDQ1334610

Andrzej Lingas

Publication date: 25 September 1994

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0925-7721(94)90018-3

zbMATH Keywords

Delaunay triangulationlinear-time algorithmGabriel graph\(\beta\)-skeletons

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Optimal and suboptimal robust algorithms for proximity graphs ⋮ A linear-time construction of the relative neighborhood graph within a histogram ⋮ A Low Arithmetic-Degree Algorithm for Computing Proximity Graphs ⋮ $$\beta $$-skeletons for a Set of Line Segments in $$R^2 $$ ⋮ Fast algorithms for computing \(\beta\)-skeletons and their relatives. ⋮ New sequential and parallel algorithms for computing the \(\beta\)-spectrum

Cites Work

• Unnamed Item
• A linear-time algorithm for a special case of disjoint set union
• The relative neighbourhood graph of a finite planar set
• Relative neighborhood graphs in three dimensions
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• Two algorithms for constructing a Delaunay triangulation