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