Search Results

Documents authored by Savić, Marko

Document
DOI: 10.4230/LIPIcs.ESA.2021.5
The Voronoi Diagram of Rotating Rays With applications to Floodlight Illumination

Authors: Carlos Alegría, Ioannis Mantas, Evanthia Papadopoulou, Marko Savić, Hendrik Schrezenmaier, Carlos Seara, and Martin Suderland

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

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.
Cite as

Carlos Alegría, Ioannis Mantas, Evanthia Papadopoulou, Marko Savić, Hendrik Schrezenmaier, Carlos Seara, and Martin Suderland. The Voronoi Diagram of Rotating Rays With applications to Floodlight Illumination. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ESA.2021.5},
  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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact