simp1eton's blog

Finding the maximal convex hull polygon
By simp1eton, 14 years ago, In English
Hi all,

I have a question about the maximal convex hull polygon. You are given N points on a 2D plane. Each point has a value X. You want to find the convex polygon such that the sum of the value of the points on the perimeter of the polygon is maximal. Output the maximal sum.

I have an N^4 DP solution. as follows.

I choose a point i and sort all the other points around this point according to angle (similar to convex hull graham scan). Then, I write the following bottom-up dp formulation:

DP[B][A] stores the best convex polygon with the last two points at B and A.

Then I calculate DP[C][B] for all C such that C-B-A is convex and I-C-B is convex.

The DP has a runtime of N^3. As I am doing this DP for all vertices I, the algorithm has a total runtime of N^4.

However, I think that there is a better algorithm with a runtime of N^3. Does anyone know this algorithm? Can someone give me some hints?

Thanks in advance!
  • Vote: I like it
  • 0
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Anyone?

This is the problem: http://www.z-trening.com/tasks.php?show_task=5000000255
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I saw the task.

I am sorry, but I cant understand why is example output 4.

I think it should be 5 , plz clarify.

-----------------------------


EDIT: got it .

→ Reply
14 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
The DP runtime can be O(n^2) for each point.
First, sort other points by polar angle for each point. This is O(n^2logn). Then we can handle the DP by a rotating sweepline, it is O(n^3). So, total is O(n^2logn + n^3)=O(n^3).
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
More details, you can see here.
→ Reply