Apply greedy algorithm to the problem of the minimum length

Apply greedy algorithm to the problem of the minimum length triangulation of a convex polygon. How far can greedy be away from optimum? Show the worst case for a pentagon

Solution

The greedy triangulation (GT) of a set S of n points in the plane is the triangulation obtained by starting with the empty set and at each step adding the shortest compatible edge between two of the points, where a compatible edge is defined to be an edge that crosses none of the previously added edges.

O(n log n) and space O(n) for points uniformly distributed over any convex region. The algorithm is easy to implement and performs well in practice. A variant of this algorithm should also be fast for many other distributions.

an edge can be greedy only if one of two small half-disks centered at its midpoint contains no points from S. This necessary condition for greedy edges allows us to prove a number of properties about the greedy triangulation for uniformly distributed points drawn from a convex compact region C. We are able to prove that all edges in a greedy triangulation of uniformly distributed points are expected either to be short or to have both endpoints near the boundary of C. Furthermore, we expect that only O(n log n) pairs of points are either short enough or have both endpoints close enough to the boundary of C to be in the greedy triangulation. Finally, we expect that only O(n) pairs of points in S satisfy the condition that at least one of the two half-disks centered at the midpoint of the pair is empty