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.
[ Parent
| on HN ]
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.
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