Greedy triangulation

Greedy triangulation

Polygon Greedy triangulation steps. On each step a new edge (red) is added joining the nearest pair of vertex, without crossing a previously edge
Class	Search algorithm
Data structure	Priority queue Spatial database
Worst-case performance	${\displaystyle O(|V|\cdot \log |V|)}$
Best-case performance	${\displaystyle O(|V|)}$

The greedy triangulation is a method to compute a polygon triangulation or a point set triangulation using a greedy algorithm, which adds edges one by one to the solution in strict increasing order by length, with the condition that an edge cannot cut a previously inserted edge. ^{[1] [2]}

References

1. J. Loera, J. Rambau and F. Santos (2010), Triangulations: Structures and Algorithms (2nd revised ed.), Springer-Verlag, ISBN   9783642129711 Chapter 3: Polygon Triangulation: pp.103.
2. Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised ed.), Springer-Verlag, ISBN   3-540-65620-0