Problem 2 Apply greedy algorithm to the problem of the minim

Problem 2:

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

Greedy algorithm to the problem of the minimum length triangulation of a convex polygon:

Definition of Triangulation:

-- a set T of chords of a convex polygon P that divide the polygon into disjoint triangles.

Minimum length triangulation(MLT):

     -- Given a convex polygon P=(v1, …, vn)

     -- Form Triangles by sides and chords of P.

-- Find a triangulation that minimizes the sum of the lengths of the triangles in the triangulations.

Example of triangulating a convex polygon:

DATA STRUCTURE:

Heap – a complete binary tree to hold all of diagonals.

-- Build-Heap(E)

-- Heapify (E, i)

HeapSort algorithm:

-- to get the minimum length triangulation.

Remove diagonals from set E.

       -- Heap-delete(E,i)

Add new diagonals

       -- Heap-Insert(E)

Algorithms for MLT:

Given a convex polygon P(v1…v n)

Find the minimum length triangulation for P(v1…v n)

Algorithms

   -- Greedy-1 Algorithm

   -- Greedy Algorithm

Greedy-1 Algorithm for MLT:

Step 1. Put all of vertices of convex polygon P into set V.

Step 2. Put all of next-neighbor diagonals into set E. For example, (k, k+2) is the next-neighbor diagonal between the vertices v k and v k+2.

Step 3. Find the minimum diagonal (k, k+2) in E, and insert it into the result set M of the minimum length triangulation of the convex polygon P.

Step 4. Remove the vertex v k+1 from set V.

Step 5. Remove all diagonals which are related to the removed vertex in set V in the last step.

Step 6.Update Eto add unexisted next- nighbor diagonal for the vertices v k and v k+2 such as (k, k+3),(k+2, k-1).

Step 7. Check if E is NOT empty, go back step 3 to repeat; otherwise return the result M.

The greedy triangulation (GT) of a set 5\' 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. In this paper we present an algorithm that computes the greedy triangulation in expected time 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.

Performance

   -- Greedy algorithm is between O(n^2) and O(n^3)

-- Greedy-1 algorithm is O(nlgn)   

Result of MLT

    -- For a convex polygon P(V), using different algorithms may get different results.

How far can greedy be away from optimum?

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage^[1] with the hope of finding a global optimum. In many problems, a greedy strategy does not in general produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution in a reasonable time.

For example, a greedy strategy for the traveling salesman problem (which is of a high computational complexity) is the following heuristic: \"At each stage visit an unvisited city nearest to the current city\". This heuristic need not find a best solution, but terminates in a reasonable number of steps; finding an optimal solution typically requires unreasonably many steps. In mathematical optimization, greedy algorithms solve combinatorial problems having the properties of matroids.

Show the worst case for a pentagon:

We have shown how to do the update step in O(n) time, using a modification of the linear-time algorithm for computing the Voronoi diagram of a convex polygon , leading to an O(n 2) time and O(n) space algorithm in the worst case .