2

We have a set S consist of n points in 2D plane and a number 3<=k<=n, how should I try to find a convex polygon with number of vertices = k (the vertices are in S) which maximizing its perimeter in O(kn^5) time complexity? The hint given for me is to build a weighted, direct, no cycle graph with O(n^2) vertices and O(n^3) edges. Thank you for the help.

user
  • 135
  • 8
  • 2
    This question seems quite clear to me. What is wanted is an algorithm with the specified timing that creates a k vertex convex polygon using k of the n specified vertices having the largest perimeter of all such polygons. – deinst May 03 '14 at 13:11
  • 1
    You might find the accepted answer to [this](http://stackoverflow.com/questions/21778506/finding-largest-subset-of-points-forming-a-convex-polygon) question helpful as it finds the max value to k in O(N^4). Modifying the algorithm (particularly the one I mention in the accepted answer's comments as that is the solution to your hint, if you add the edge weights) it to suit your purposes should be able to find the max perimeter in O(N^5). – Nuclearman May 04 '14 at 02:52
  • @Nuclearman: I am still thinking how to construct that O(n^2) vertices when I have n points. – user May 04 '14 at 03:42

0 Answers0