3 ms·
A simple, fast solution to this type of problem involves applying Welzl's algorithm for an expected O(n polylog n) solution.
by stevenf 12y ago
A simple, fast solution to this type of problem involves applying Welzl's algorithm for an expected O(n polylog n) solution.
- TheLoneWolfling 12y agoI thought Welzl's algorithm was for circles, not regular polygons.
- shasta 12y agoWell, 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.