Greedy triangulation

From HandWiki
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 performance[math]\displaystyle{ O(|V| \cdot \log |V|) }[/math]
Best-case performance[math]\displaystyle{ O(|V|) }[/math]

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

  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.
  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, https://archive.org/details/computationalgeo00berg