![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/2/28/Polygon_Greedy_triangulation_steps.svg/640px-Polygon_Greedy_triangulation_steps.svg.png&w=640&q=50)
Greedy triangulation
From Wikipedia, the free encyclopedia
The Greedy Triangulation is a method to compute a polygon triangulation or a Point set triangulation using a greedy schema, 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]
Quick Facts Class, Data structure ...
![]() 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 | |
Worst-case performance | |
Best-case performance |
Close