News for hackers. Stuff that matters.
Re:Finding a minimum polygon of a set of points by chaoxu on Tuesday April 07, 2015 @12:31AM (#9332028)
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))

One can transform the problem to the following, and solve it in around O(n^7) time. http://dl.acm.org/citation.cfm?id=73853

There probably exist faster algorithm for this special case using smarter parametric search...

Re:Finding a minimum polygon of a set of points by jbattle on Monday April 06, 2015 @05:12PM (#9330727)
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)...

http://en.wikipedia.org/wiki/Gift_wrapping_algorithm

Re:Finding a minimum polygon of a set of points by jgunsch on Monday April 06, 2015 @07:19PM (#9331246)
The algorithm seems similar to the Graham scan [1], but in either case it doesn't calculate a _regular_ polygon, which makes the problem trickier.

[1] http://en.wikipedia.org/wiki/Graham_scan

Re:Finding a minimum polygon of a set of points by TheLoneWolfling on Monday April 06, 2015 @04:31PM (#9330538)
I'm probably missing something, because I don't see what's so difficult about this.

You can do this as a "rolling" algorithm. Start with three points, defining a triangle. Then repeatedly add the next point.

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.

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.

Now, this isn't particularly fast - O(n^3) I think, but it's still faster than spinning up a LP solver.

(Again, I'm probably missing something.)

Re:Finding a minimum polygon of a set of points by Trombone12 on Monday April 06, 2015 @05:11PM (#9330720)
The solution demonstrated on the page seems to ask for the n-gon that circumscribes n randomly placed points, which isn't the same as the smallest convex hull that contains them. I'm not sure why the polygon should have the same number sides as there are points to contain, especially since the original tweet asks for a convex hull, but there you go.
Re:Finding a minimum polygon of a set of points by TheLoneWolfling on Monday April 06, 2015 @05:43PM (#9330868)
Oh, ok.

That makes much more sense.

Re:Finding a minimum polygon of a set of points by Strilanc on Monday April 06, 2015 @06:12PM (#9330994)
FYI, the algorithm you were describing was to compute a convex hull. It can be done in O(n lg n) time by sorting the points by angle w.r.t. some starting point and then "gift wrapping".

You can find where to add a new point in O(lg h) time with a binary search, but you may need to eject O(h) old points. Points can only be ejected once, so there might still be some nice aggregate bound in terms of n.

http://en.wikipedia.org/wiki/Convex_hull_algorithms

Re:Finding a minimum polygon of a set of points by laex on Monday April 06, 2015 @07:07PM (#9331209)
Some time back, I wrote a simple convex hull computing code in Go. If anyone's interested: https://github.com/hemantasapkota/go-convexhull
Re:Finding a minimum polygon of a set of points by nilkn on Monday April 06, 2015 @06:49PM (#9331151)
As far as I can tell, this is actually finding the smallest regular n-gon which contains n points.
Re:Finding a minimum polygon of a set of points by stevenf on Monday April 06, 2015 @05:42PM (#9330862)
A simple, fast solution to this type of problem involves applying Welzl's algorithm for an expected O(n polylog n) solution.
Re:Finding a minimum polygon of a set of points by shasta on Monday April 06, 2015 @06:18PM (#9331028)
Well, there are sets of four points whose minimal containing square is not defined by any three of the points. That makes me suspicious that you're not going to get this plan to work.

And playing with the program, I find minimal pentagons that seem to be defined by 5 points.

Re:Finding a minimum polygon of a set of points by TheLoneWolfling on Monday April 06, 2015 @05:46PM (#9330880)
I thought Welzl's algorithm was for circles, not regular polygons.
Re:Finding a minimum polygon of a set of points by mattdesl on Monday April 06, 2015 @06:02PM (#9330953)
Re:Finding a minimum polygon of a set of points by nilkn on Monday April 06, 2015 @11:05PM (#9331813)
I played around with this a while ago:

http://bl.ocks.org/zpconn/11387143