License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.5
URN: urn:nbn:de:0030-drops-145865
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14586/
Alegría, Carlos ;
Mantas, Ioannis ;
Papadopoulou, Evanthia ;
Savić, Marko ;
Schrezenmaier, Hendrik ;
Seara, Carlos ;
Suderland, Martin
The Voronoi Diagram of Rotating Rays With applications to Floodlight Illumination
Abstract
We introduce the Voronoi Diagram of Rotating Rays, a Voronoi structure where the input sites are rays, and the distance function is the counterclockwise angular distance between a point and a ray-site. This novel Voronoi diagram is motivated by illumination and coverage problems, where a domain has to be covered by floodlights (wedges) of uniform angle, and the goal is to find the minimum angle necessary to cover the domain. We study the diagram in the plane, and we present structural properties, combinatorial complexity bounds, and a construction algorithm. If the rays are induced by a convex polygon, we show how to construct the ray Voronoi diagram within this polygon in linear time. Using this information, we can find in optimal linear time the Brocard angle, the minimum angle required to illuminate a convex polygon with floodlights of uniform angle. This last algorithm improves upon previous results, settling an interesting open problem.
BibTeX - Entry
@InProceedings{alegria_et_al:LIPIcs.ESA.2021.5,
author = {Alegr{\'\i}a, Carlos and Mantas, Ioannis and Papadopoulou, Evanthia and Savi\'{c}, Marko and Schrezenmaier, Hendrik and Seara, Carlos and Suderland, Martin},
title = {{The Voronoi Diagram of Rotating Rays With applications to Floodlight Illumination}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {5:1--5:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-204-4},
ISSN = {1868-8969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14586},
URN = {urn:nbn:de:0030-drops-145865},
doi = {10.4230/LIPIcs.ESA.2021.5},
annote = {Keywords: rotating rays, Voronoi diagram, oriented angular distance, Brocard angle, floodlight illumination, coverage problems, art gallery problems}
}
|
Keywords: |
|
rotating rays, Voronoi diagram, oriented angular distance, Brocard angle, floodlight illumination, coverage problems, art gallery problems |
|
Collection: |
|
29th Annual European Symposium on Algorithms (ESA 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
31.08.2021 |
