- Alegria, Carlos
- Mantas, Ioannis
- Papadopoulou, Evanthia
- Savic, Marko
- Seara Ojea, Carlos
- Suderland, Martin
34 p.
This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/[10.1007/s00453-025-01368-y], 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., Acknowledgements: Initial discussions took place at the Intensive Research Program in Discrete, Combinatorial and Computational Geometry in Barcelona, Spain, in 2018. We are grateful to the 44 organizers for providing the platform to meet and collaborate. We also thank Hendrik Schrezenmaier 45 for early discussions related to the results of Section 3.1. Funding: Carlos Alegría: Supported by projects MIUR Proj. “AHeAD” no 20174LF3T8 and European Union’s Horizon 2020 No. 734922. Ioannis Mantas: Supported in part by SNF project 200021E_154387. Evanthia Papadopoulou: Supported in part by SNF projects 200021E_154387 and 200021E_201356. Marko Savić: Supported by the Ministry of Education, Science and Technological Development of the Republic of Serbia (Grant No. 451-03-68/2022-14/200125), and the Provincial Secretariat for Higher Education and Scientific Research, Province of Vojvodina. Carlos Seara: Supported by projects PID2023-150725NB-I00 funded by Ministerio de Ciencia e Innovación/AEI/10.13039/501100011033 and European Union’s Horizon 2020 No. 734922. Martin Suderland: Supported in part by SNF project 200021E_201356., Peer Reviewed, Postprint (author's final draft)