Greedy triangulation can be efficiently implemented in the average case

DOI10.1007/3-540-50728-0_48OpenAlexW1596144427MaRDI QIDQ6118596

Andrzej Lingas

Publication date: 28 February 2024

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-50728-0_48

Mathematics Subject Classification ID

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

Cites Work

• On the average length of Delaunay triangulations
• The greedy and Delaunay triangulations are not bad in the average case
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation
• Optimal Expected-Time Algorithms for Closest Point Problems

This page was built for publication: Greedy triangulation can be efficiently implemented in the average case