We consider the problem of placing a star R on a set S of n points in the plane in order to maximize a given ob- jective function. A star R is a set of m rays {r1, rm} in R2, emanating from a point p such that the angle be- tween two consecutive rays is 2π/m. The cone defined by two consecutive rays with apex p is k-occupied if it contains at least k points of S. We design algorithms to compute placements of R that maximize or minimize the number of k-occupied cones of R. Our main result is an O(nm 3 log(m) + nmlog(nm))) time algorithm for finding a placement of R that maximizes the number of k-occupied cones.

17th Canadian Conference on Computational Geometry, CCCG 2005
School of Computer Science

Bose, P, & Morrison, J. (Jason). (2005). Optimally placing a star on a point set. In Proceedings of the 17th Canadian Conference on Computational Geometry, CCCG 2005 (pp. 179–182).