Greedy triangulation

Greedy triangulation
Polygon Greedy triangulation steps
Polygon Greedy triangulation steps. On each step a new edge (red) is added joining the nearest pair of vertex, without crossing a previously edge
ClassSearch algorithm
Data structure
Worst-case performanceO(|V|⋅log⁡|V|)
Best-case performanceO(|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.