greedy triangulation

{{Infobox algorithm

|class=Search algorithm

|image=Image:Polygon Greedy triangulation steps.svg

|caption = Polygon Greedy triangulation steps. On each step a new edge (red) is added joining the nearest pair of vertex, without crossing a previously edge

|data= * Priority queue

• Spatial database

|time= $O(|V|\; \backslash cdot\; \backslash log\; |V|)$

|best-time= $O(|V|)$

|average-time=

|space=

|optimal=

|complete=

}}

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.

{{Citation|author = J. Loera, J. Rambau and F. Santos| year = 2010 | title = Triangulations: Structures and Algorithms | publisher = Springer-Verlag | edition = 2nd revised | isbn=9783642129711}} Chapter 3: Polygon Triangulation: pp.103.

{{Citation | author = Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf | year = 2000 | title = Computational Geometry | publisher = Springer-Verlag | edition = 2nd revised | isbn = 3-540-65620-0 | url-access = registration | url = https://archive.org/details/computationalgeo00berg }}