The problem seems to be: find the smallest regular k-gon that covers all the points. (now, assume the total number of points is n, and k = O(n))<p>One can transform the problem to the following, and solve it in around O(n^7) time.
<a href="http://dl.acm.org/citation.cfm?id=73853" rel="nofollow">http://dl.acm.org/citation.cfm?id=73853</a><p>There probably exist faster algorithm for this special case using smarter parametric search...
The animation on wiki seems broken, but the gift wrapping algorithm is easy to understand and implement and gives good results (though different from what is presented here)...<p><a href="http://en.wikipedia.org/wiki/Gift_wrapping_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Gift_wrapping_algorithm</a>
I'm probably missing something, because I don't see what's so difficult about this.<p>You can do this as a "rolling" algorithm. Start with three points, defining a triangle. Then repeatedly add the next point.<p>To add a point, first check if it's inside the (convex) polygon found so far. If it is, you're done. Just continue to the next point to add.<p>If it isn't, you walk along both directions along the (convex) polygon until you hit the first point that doesn't violate the convexity constraint. (Just compare slopes of the lines between the next point and the target point, and the target point and the point to be added). Then just splice it in in place of the chunk removed.<p>Now, this isn't particularly fast - O(n^3) I think, but it's still faster than spinning up a LP solver.<p>(Again, I'm probably missing something.)