The Voronoi Diagram of Rotating Rays with applications to floodlight illumination
Informazioni aggiuntive
Autori
Alegría C.,
Mantas I.,
Papadopoulou E.,
Savić M.,
Seara C.,
Suderland M. G.
Tipo
Articolo pubblicato in rivista scientifica
Anno
2026
Lingua
Inglese
Sommario
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.
Parole chiave
Rotating rays Voronoi diagram, Oriented angular distance, Brocard angle, Brocard illumination, Floodlight illumination, Coverage problems
Periodico
Algorithmica
Volume
88
Numero ( Mese )
27
Diffusione
Licenza
Diritti riservati
Visibilità
Pubblico
Status open access
Green
