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
Best-case performance

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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]

References

^ 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.
^ Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised ed.), Springer-Verlag, ISBN 3-540-65620-0{{citation}}: CS1 maint: multiple names: authors list (link)

[Loera2010-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.

[bkos-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{{citation}}: CS1 maint: multiple names: authors list (link)

[1]

[2]