Greedy triangulation

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]

ClassSearch algorithm

Data structure

• Priority queue
• Spatial database

Worst-case performance${\displaystyle O(|V|\cdot \log |V|)}$

Best-case performance${\displaystyle O(|V|)}$

Quick facts Class, Data structure ...

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|)}$

Close