CODEWITHSUNDEEP
algorithmgeometry
Vikash Balasubramanian
Vikash Balasubramanian

Reputation: 3233

Finding maximum area k-gon given a set of points

I was trying to solve a practice problem in the topcoder arena: http://topcoder.bgcoder.com/print.php?id=417

According to my understanding the aim of the problem is to find a k-gon of maximum area, given a set of Points D and k<=n, n is a fixed value.

Let the Convex Hull of D = C(D)

If n=3, i have proved that such a triangle can be constructed by assuming that it's vertices are a subset of C(D). So it was quite easy to come up with a solution for k=3 : https://stackoverflow.com/a/1621913/4126652

However, for n>3, i have no idea how to do this.

Here is how i tried:

Let |C(D)| = l i.e the convex hull is an l-gon,

If n > l i am pretty sure that the k-gon with maximum area will be the convex hull itself, i.e C(D)

if n < l i am pretty sure that the vertices of the maximal k-gon will be a subset of C(D), i couldn't prove it for k>3, and i am unable to come up with an algorithm to solve even if this is a correct assumption.

Can anyone help me with this, is my approach correct? and can you help me proceed further?

Upvotes: 5

Views: 956

Answers (1)

Vikash Balasubramanian
Vikash Balasubramanian

Reputation: 3233

After breaking my head for a few hours, i figured out the solution.

It is a dynamic programming problem:

Let dp[m][o][r] denote the maximum area r-gon such that the starting vertex is m and the ending vertex is o (vertices taken in cyclic order).

Then recurrence relation will be:

dp[m][o][r] = max(dp[m][n][r-1] + area(m,n,o)), {max over all n: m < n < o}

where area(m,n,o) is the area of the triangle formed by vertices m, n and o

Upvotes: 2

Related Questions