Optimal point set partitioning using rigid motion star placement
Prosenjit K. Bose, Jason B. Morrison · 2007
We consider the problem of determining the placement of a star R on a set P of n points in the plane such that a given objective function is maximized. A star R is a set of m rays {r1,..., rm} in R 2, emanating from a point p such that the angle between two consecutive rays is 2π m. A cone defined by two consecutive rays is c-occupied if it contains at least c points of P. Our main result is an O(n 3 m 2) expected time (and O(n 3 m 2 log nm) deterministic time) algorithm to find the rigid motion placement of R that maximizes the number of c-occupied cones. We then show how this technique can be extended to solve several other optimization problems. 1