2005-01-01

# Optimally placing a star on a point set

## Publication

### Publication

*Presented at the 17th Canadian Conference on Computational Geometry, CCCG 2005 (August 2005), Windsor*

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.

Additional Metadata | |
---|---|

Conference | 17th Canadian Conference on Computational Geometry, CCCG 2005 |

Citation |
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). |