Greedy triangulation can be efficiently implemented in the average case

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

Authors: 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

Recommendations

• A space efficient greedy triangulation algorithm
• scientific article; zbMATH DE number 4064506
• Fast greedy triangulation algorithms.
• The greedy triangulation can be computed from the Delaunay triangulation in linear time
• On approximation behavior of the greedy triangulation for convex polygons

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (1)

• Greedy permutations and Finite Voronoi diagrams (media exposition)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6118596)