{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T07:23:30Z","timestamp":1773041010048,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T00:00:00Z","timestamp":1773014400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T00:00:00Z","timestamp":1773014400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,4]]},"DOI":"10.1007\/s00453-025-01368-y","type":"journal-article","created":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T06:29:24Z","timestamp":1773037764000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Voronoi Diagram of Rotating Rays with Applications to Floodlight Illumination"],"prefix":"10.1007","volume":"88","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5512-5298","authenticated-orcid":false,"given":"Carlos","family":"Alegr\u00eda","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8256-8107","authenticated-orcid":false,"given":"Ioannis","family":"Mantas","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0144-7384","authenticated-orcid":false,"given":"Evanthia","family":"Papadopoulou","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6746-4334","authenticated-orcid":false,"given":"Marko","family":"Savi\u0107","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0095-1725","authenticated-orcid":false,"given":"Carlos","family":"Seara","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6604-6381","authenticated-orcid":false,"given":"Martin","family":"Suderland","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,3,9]]},"reference":[{"key":"1368_CR1","unstructured":"Alegr\u00eda, C., Mantas, I., Papadopoulou, E., Savic, M., Seara, C., Suderland, M.: The Voronoi diagram of rotating rays with applications to floodlight illumination. In: 29th Annual European Symposium on Algorithms (ESA 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"1368_CR2","unstructured":"Alegr\u00eda-Galicia, C., Orden, D., Seara, C., Urrutia, J.: Illuminating polygons by edge-aligned floodlights of uniform angle (Brocard illumination). In: Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG 2017), pages 281\u2013284 (2017)"},{"issue":"6","key":"1368_CR3","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.ipl.2006.07.008","volume":"100","author":"F Aurenhammer","year":"2006","unstructured":"Aurenhammer, F., Drysdale, R.L.S., Krasser, H.: Farthest line segment Voronoi diagrams. Inf. Process. Lett. 100(6), 220\u2013225 (2006). https:\/\/doi.org\/10.1016\/j.ipl.2006.07.008","journal-title":"Inf. Process. Lett."},{"key":"1368_CR4","doi-asserted-by":"crossref","unstructured":"Aurenhammer, F., Klein, R., Lee, D.-T..: Voronoi Diagrams and Delaunay Triangulations. World Scientific (2013)","DOI":"10.1142\/8685"},{"key":"1368_CR5","doi-asserted-by":"publisher","unstructured":"Berman, P., Jeong, J., Kasiviswanathan, S.P., Urgaonkar, B.: Packing to angles and sectors. In Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201907), pages 171\u2013180 (2007). https:\/\/doi.org\/10.1145\/1248377.1248405","DOI":"10.1145\/1248377.1248405"},{"issue":"1","key":"1368_CR6","first-page":"23","volume":"24","author":"A Bernhart","year":"1959","unstructured":"Bernhart, A.: Polygons of pursuit. Scripta. Mathematica 24(1), 23\u201350 (1959)","journal-title":"Mathematica"},{"issue":"5","key":"1368_CR7","doi-asserted-by":"publisher","first-page":"495","DOI":"10.4169\/amer.math.monthly.122.5.495","volume":"122","author":"\u00c1 Besenyei","year":"2015","unstructured":"Besenyei, \u00c1.: The Brocard angle and a geometrical gem from Dmitriev and Dynkin. Am. Math. Mon. 122(5), 495\u2013499 (2015). https:\/\/doi.org\/10.4169\/amer.math.monthly.122.5.495","journal-title":"Am. Math. Mon."},{"issue":"1\u20132","key":"1368_CR8","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1142\/S0218195997000090","volume":"7","author":"P Bose","year":"1997","unstructured":"Bose, P., Guibas, L.J., Lubiw, A., Overmars, M., Souvaine, D., Urrutia, J.: The floodlight problem. Int. J. Comp. Geo. Appl. 7(1\u20132), 153\u2013163 (1997). https:\/\/doi.org\/10.1142\/S0218195997000090","journal-title":"Int. J. Comp. Geo. Appl."},{"issue":"1","key":"1368_CR9","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.comgeo.2007.01.004","volume":"43","author":"M Cary","year":"2010","unstructured":"Cary, M., Rudra, A., Sabharwal, A., Vee, E.: Floodlight illumination of infinite wedges. Comput. Geom. 43(1), 23\u201334 (2010). https:\/\/doi.org\/10.1016\/j.comgeo.2007.01.004","journal-title":"Comput. Geom."},{"key":"1368_CR10","volume-title":"A sequel to the first six books of the elements of Euclid","author":"J Casey","year":"1888","unstructured":"Casey, J.: A sequel to the first six books of the elements of Euclid. Dublin University Press, Dublin (1888)"},{"key":"1368_CR11","unstructured":"Contreras, F., Czyzowicz, J., Fraiji, N., Urrutia, J.: Illuminating triangles and quadrilaterals with vertex floodlights. In Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG\u201998) (1998)"},{"key":"1368_CR12","doi-asserted-by":"crossref","unstructured":"Contreras, F., Czyzowicz, J., Rivera-Campo, E., Urrutia, J.: Optimal floodlight illumination of stages. In: Proceedings of the 14th annual Symposium on Computational Geometry (SoCG 1998), pages 409\u2013410 (1998)","DOI":"10.1145\/276884.276932"},{"issue":"2","key":"1368_CR13","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/s00373-015-1543-4","volume":"31","author":"J Czyzowicz","year":"2015","unstructured":"Czyzowicz, J., Dobrev, S., Joeris, B., Kranakis, E., Krizanc, D., Ma\u0148uch, J., Morales-Ponce, O., Opatrny, J., Stacho, L., Urrutia, J.: Monitoring the plane with rotating radars. Graphs and Combinatorics 31(2), 393\u2013405 (2015). https:\/\/doi.org\/10.1007\/s00373-015-1543-4","journal-title":"Graphs and Combinatorics"},{"key":"1368_CR14","unstructured":"de\u00a0Berg, M., Gudmundsson, J., Haverkort, H., Horton, M.: Voronoi diagrams with rotational distance costs. In: Abstracts of the Computational Geometry Week: Young Researchers Forum (CG:YRF) (2017)"},{"issue":"4","key":"1368_CR15","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/j.ipl.2007.08.009","volume":"105","author":"J Dietel","year":"2008","unstructured":"Dietel, J., Hecker, H.-D., Spillner, A.: A note on optimal floodlight illumination of stages. Inf. Process. Lett. 105(4), 121\u2013123 (2008). https:\/\/doi.org\/10.1016\/j.ipl.2007.08.009","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"1368_CR16","first-page":"167","volume":"10","author":"NA Dmitriev","year":"1946","unstructured":"Dmitriev, N.A., Dynkin, E.B.: On characteristic roots of stochastic matrices. Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya 10(2), 167\u2013184 (1946)","journal-title":"Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya"},{"issue":"1","key":"1368_CR17","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/0020-0190(95)00129-Z","volume":"56","author":"V Estivill-Castro","year":"1995","unstructured":"Estivill-Castro, V., O\u2019Rourke, J., Urrutia, J., Dianna, X.: Illumination of polygons with vertex lights. Inf. Process. Lett. 56(1), 9\u201313 (1995). https:\/\/doi.org\/10.1016\/0020-0190(95)00129-Z","journal-title":"Inf. Process. Lett."},{"key":"1368_CR18","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.tcs.2013.08.008","volume":"532","author":"C Fan","year":"2014","unstructured":"Fan, C., Luo, J., Wang, W., Zhu, B.: Voronoi diagram with visual restriction. Theoret. Comput. Sci. 532, 31\u201339 (2014). https:\/\/doi.org\/10.1016\/j.tcs.2013.08.008","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"1368_CR19","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/BF02579170","volume":"6","author":"S Hart","year":"1986","unstructured":"Hart, S., Sharir, M.: Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes. Combinatorica 6(2), 151\u2013177 (1986). https:\/\/doi.org\/10.1007\/BF02579170","journal-title":"Combinatorica"},{"key":"1368_CR20","unstructured":"Haverkort, H., Klein, R.: Hyperbolae are the locus of constant angle difference (2021). arXiv preprint arXiv:2112.00454"},{"issue":"4","key":"1368_CR21","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(89)90136-1","volume":"33","author":"J Hershberger","year":"1989","unstructured":"Hershberger, J.: Finding the upper envelope of $$n$$ line segments in $${O}(n\\log n)$$ time. Inf. Process. Lett. 33(4), 169\u2013174 (1989). https:\/\/doi.org\/10.1016\/0020-0190(89)90136-1","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"1368_CR22","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s10998-008-8177-3","volume":"57","author":"DP Ismailescu","year":"2008","unstructured":"Ismailescu, D.P.: Illuminating a convex polygon with vertex lights. Period. Math. Hung. 57(2), 177\u2013184 (2008). https:\/\/doi.org\/10.1007\/s10998-008-8177-3","journal-title":"Period. Math. Hung."},{"key":"1368_CR23","doi-asserted-by":"crossref","unstructured":"Ito, H., Uehara, H., Yokoyama, M.: NP-completeness of stage illumination problems. In: Proceedings of the 2nd Japanese Conference on Discrete and Computational Geometry (JCDCG\u201998:), pages 158\u2013165. Springer (1998)","DOI":"10.1007\/978-3-540-46515-7_12"},{"key":"1368_CR24","doi-asserted-by":"crossref","unstructured":"Klein, R.: Concrete and abstract Voronoi diagrams, volume 400. Springer Science & Business Media (1989)","DOI":"10.1007\/3-540-52055-4"},{"issue":"9","key":"1368_CR25","doi-asserted-by":"publisher","first-page":"885","DOI":"10.1016\/j.comgeo.2009.03.002","volume":"42","author":"R Klein","year":"2009","unstructured":"Klein, R., Langetepe, E., Nilforoushan, Z.: Abstract Voronoi diagrams revisited. Comp. Geom. Theory Appl. 42(9), 885\u2013902 (2009). https:\/\/doi.org\/10.1016\/j.comgeo.2009.03.002","journal-title":"Comp. Geom. Theory Appl."},{"key":"1368_CR26","doi-asserted-by":"publisher","unstructured":"Klein, R., Lingas, A.: Hamiltonian abstract Voronoi diagrams in linear time. In Proceedings of the 5th International Symposium on Algorithms and Computation (ISAAC 1994), pages 11\u201319. Springer (1994). https:\/\/doi.org\/10.1007\/3-540-58325-4_161","DOI":"10.1007\/3-540-58325-4_161"},{"key":"1368_CR27","doi-asserted-by":"publisher","unstructured":"Kranakis, E., Krizanc, D., Morales, O.: Maintaining connectivity in sensor networks using directional antennae. In: Theoretical Aspects of Distributed Computing in Sensor Networks, pages 59\u201384. Springer (2011). https:\/\/doi.org\/10.1007\/978-3-642-14849-1_3","DOI":"10.1007\/978-3-642-14849-1_3"},{"key":"1368_CR28","doi-asserted-by":"publisher","unstructured":"Neishaboori, A., Saeed, A., Harras, K.A., Mohamed, A.: On target coverage in mobile visual sensor networks. In: Proceedings of the 12th ACM International Symposium on Mobility Management and Wireless Access (MobiWac\u201915), pages 39\u201346 (2014). https:\/\/doi.org\/10.1145\/2642668.2642671","DOI":"10.1145\/2642668.2642671"},{"key":"1368_CR29","doi-asserted-by":"publisher","unstructured":"Nilsson, B.J., Orden, D., Palios, L., Seara, C., \u017byli\u0144ski, P.: Illuminating the x-axis by $$\\alpha $$-Floodlights. In Hee-Kap Ahn and Kunihiko Sadakane, editors, 32nd International Symposium on Algorithms and Computation (ISAAC 2021), volume 212 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1\u201311:12. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2021.11","DOI":"10.4230\/LIPIcs.ISAAC.2021.11"},{"key":"1368_CR30","volume-title":"Spatial tessellations: concepts and applications of Voronoi diagrams","author":"A Okabe","year":"2009","unstructured":"Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial tessellations: concepts and applications of Voronoi diagrams, vol. 501. John Wiley & Sons, New Jersey (2009)"},{"key":"1368_CR31","volume-title":"Art gallery theorems and algorithms","author":"J O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke, J.: Art gallery theorems and algorithms, vol. 57. Oxford University Press, Oxford (1987)"},{"key":"1368_CR32","unstructured":"O\u2019Rourke, J.: Visibility. In Handbook of Discrete and Computational Geometry, pages 875\u2013896. CRC Press (2017)"},{"key":"1368_CR33","unstructured":"O\u2019Rourke, J.: Thomas Shermer, and Ileana Streinu. Illuminating convex polygons with vertex floodlights. In: Proceedings of the 7th Canadian Conference on Computational Geometry (CCCG\u201995), pages 151\u2013156 (1995)"},{"key":"1368_CR34","unstructured":"Papadopoulou, E., Suderland, M., Wang, Z.: A collapse algorithm for farthest Voronoi diagrams in three dimensions. In: Proceedings of the 41st European Workshop on Computational Geometry (EuroCG 2025), pages 30:1\u201330:9 (2025)"},{"issue":"3","key":"1368_CR35","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF02574384","volume":"12","author":"M Sharir","year":"1994","unstructured":"Sharir, M.: Almost tight upper bounds for lower envelopes in higher dimensions. Discrete Comput. Geom. 12(3), 327\u2013345 (1994). https:\/\/doi.org\/10.1007\/BF02574384","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"1368_CR36","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(91)90030-L","volume":"37","author":"S Skyum","year":"1991","unstructured":"Skyum, S.: A simple algorithm for computing the smallest enclosing circle. Inf. Process. Lett. 37(3), 121\u2013125 (1991). https:\/\/doi.org\/10.1016\/0020-0190(91)90030-L","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"1368_CR37","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0925-7721(97)00027-8","volume":"10","author":"W Steiger","year":"1998","unstructured":"Steiger, W., Streinu, I.: Illumination by floodlights. Comput. Geom. 10(1), 57\u201370 (1998). https:\/\/doi.org\/10.1016\/S0925-7721(97)00027-8","journal-title":"Comput. Geom."},{"key":"1368_CR38","doi-asserted-by":"publisher","unstructured":"Taki, T., Hasegawa, J.-I., Fukumura, T.: Development of motion analysis system for quantitative evaluation of teamwork in soccer games. In: Proceedings of the 3rd IEEE International Conference on Image Processing, volume\u00a03, pages 815\u2013818. IEEE (1996). https:\/\/doi.org\/10.1109\/ICIP.1996.560865","DOI":"10.1109\/ICIP.1996.560865"},{"issue":"2","key":"1368_CR39","doi-asserted-by":"publisher","first-page":"876","DOI":"10.1109\/JSEN.2014.2310180","volume":"15","author":"D Tao","year":"2015","unstructured":"Tao, D., Tin-Yu, W.: A survey on barrier coverage problem in directional sensor networks. IEEE Sens. J. 15(2), 876\u2013885 (2015). https:\/\/doi.org\/10.1109\/JSEN.2014.2310180","journal-title":"IEEE Sens. J."},{"issue":"3","key":"1368_CR40","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0925-7721(01)00024-4","volume":"21","author":"CD T\u00f3th","year":"2002","unstructured":"T\u00f3th, C.D.: Art galleries with guards of uniform range of vision. Comput. Geom. 21(3), 185\u2013192 (2002). https:\/\/doi.org\/10.1016\/S0925-7721(01)00024-4","journal-title":"Comput. Geom."},{"issue":"3","key":"1368_CR41","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/s00454-003-2797-9","volume":"30","author":"CD T\u00f3th","year":"2003","unstructured":"T\u00f3th, C.D.: Illuminating disjoint line segments in the plane. Discrete Comp. Geom. 30(3), 489\u2013505 (2003)","journal-title":"Discrete Comp. Geom."},{"issue":"1","key":"1368_CR42","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0012-365X(02)00583-6","volume":"265","author":"CD T\u00f3th","year":"2003","unstructured":"T\u00f3th, C.D.: Illumination of polygons by $$45^{\\circ }$$-floodlights. Discret. Math. 265(1), 251\u2013260 (2003). https:\/\/doi.org\/10.1016\/S0012-365X(02)00583-6","journal-title":"Discret. Math."},{"key":"1368_CR43","doi-asserted-by":"crossref","unstructured":"Urrutia, J.: Art gallery and illumination problems. In Handbook of Computational Geometry, pages 973\u20131027. Elsevier (2000)","DOI":"10.1016\/B978-044482537-7\/50023-1"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01368-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01368-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01368-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T06:29:38Z","timestamp":1773037778000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01368-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,9]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["1368"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01368-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,9]]},"assertion":[{"value":"30 April 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 December 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 March 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"27"}}