Find the minimum length triangulation of a pentagon using greedy algorithm and o

Question

Find the minimum length triangulation of a pentagon using greedy algorithm and optimal algorithm. Consider the following pentagon for this algorithm. Note that the sum of two diagonals (blue) found in greedy algorithm is always greater than the sum of two diagonals (red) found in optimal algorithm. You can assume the horizontal blue diagonal length 1.

How far can greedy be away from optimum? Please give the answer in a ratio = greedy/optimal. For example, if the sum of blue diagonals is 2.2, and the sum of red diagonals is 2.1, the ratio should be 2.2/2.1.

Explanation / Answer

#include <bits/stdc++.h>
#define MAX 1000000.0
using namespace std;

struct Point
{
int x, y;
};

double min(double x, double y)
{
return (x <= y)? x : y;
}

double distance(Point p1, Point p2)
{
return sqrt((p1.x - p2.x)*(p1.x - p2.x) +
(p1.y - p2.y)*(p1.y - p2.y));
}

double cost(Point points[], int i, int j, int k)
{
Point p1 = points[i], p2 = points[j], p3 = points[k];
return distance(p1, p2) + distance(p2, p3) + distance(p3, p1);
}

double TriangulationGreedy(Point points[], int i, int j)
{

if (j < i+2)
return 0;


double res = MAX;


for (int k=i+1; k<j; k++)
res = min(res, (TriangulationGreedy(points, i, k) + TriangulationGreedy(points, k, j) +
cost(points, i, k, j)));
return res;
}

double TriangulationOptimal(Point points[], int n)
{

if (n < 3)
return 0;


double T[n][n];


for (int gap = 0; gap < n; gap++)
{
for (int i = 0, j = gap; j < n; i++, j++)
{
if (j < i+2)
T[i][j] = 0.0;
else
{
T[i][j] = MAX;
for (int k = i+1; k < j; k++)
{
double val = T[i][k] + T[k][j] + cost(points,i,j,k);
if (T[i][j] > val)
T[i][j] = val;
}
}
}
}
return T[0][n-1];
}
int main()
{
Point points[] = {{0, 0}, {1, 0}, {2, 1}, {1, 2}, {0, 2}};
int n = sizeof(points)/sizeof(points[0]);
cout << "Using greedy "<<TriangulationGreedy(points, 0, n-1);
cout << " Using Optimal "<<TriangulationOptimal(points,n);
cout<<" Ratio is "<<TriangulationGreedy(points, 0, n-1)/TriangulationOptimal(points,n);

return 0;
}

============================================================================

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.