The Voronoi Diagram of Rotating Rays with Applications to Floodlight Illumination

We study the Voronoi Diagram of Rotating Rays, a Voronoi structure where the input sites are rays and the distance function between a point and a site/ray is their counterclockwise angular distance. This novel Voronoi diagram is motivated by illumination and coverage problems, where a domain must be covered by floodlights, which are wedges of uniform angle, and the goal is to find the minimum angle necessary to cover the domain. This angle is called the Brocard angle and it is encoded in the Voronoi diagram of rotating rays. We study the diagram in the plane and present its structural properties, its combinatorial complexity bounds, and a construction algorithm. If the rays are induced by a convex polygon, we show how to construct the rotating rays Voronoi diagram within the polygon in optimal linear time. We can thus compute the Brocard angle of the polygon in the same time. Floodlights are used to model devices with limited sensing range, like surveillance cameras or directional antennas. In this context, the Brocard angle reveals the minimum range necessary for a set of devices to cover a domain.