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 transf

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 http://dl.acm.org/citation.cfm?id=73853 There probably exist faster algorithm for this special case using smarter parametric search...