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 ℝ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 3m2) expected time (and O(n3m2 lognm) 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.

Additional Metadata
Conference 19th Annual Canadian Conference on Computational Geometry, CCCG 2007
Citation
Bose, P, & Morrison, J. (Jason). (2007). Optimal point set partitioning using rigid motion star placement. Presented at the 19th Annual Canadian Conference on Computational Geometry, CCCG 2007.