Back
Papadopoulou_2026_Springer_Algorithmica_Rotating_Rays_Voronoi_diagram.pdf
Public access from
09/03/2027
Journal article

The Voronoi Diagram of Rotating Rays with applications to floodlight illumination

Show more…
  • 2026
Published in:
  • Algorithmica. - 2026, vol. 88, no. 27
Rotating rays Voronoi diagram
Oriented angular distance
Brocard angle
Brocard illumination
Floodlight illumination
Coverage problems
English 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.
Collections
Language
  • English
Classification
Computer science and technology
License
Rights reserved
Open access status
green
Identifiers
Persistent URL
https://n2t.net/ark:/12658/srd1334958
Statistics
Document views: 0 File downloads:
  • Papadopoulou_2026_Springer_Algorithmica_Rotating_Rays_Voronoi_diagram.pdf: 0