Greedy triangulation can be efficiently implemented in the average case

DOI10.1007/3-540-50728-0_48MaRDI QIDQ6118596zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cites work

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

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)