{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T04:05:34Z","timestamp":1751601934698,"version":"3.41.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T00:00:00Z","timestamp":1748390400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T00:00:00Z","timestamp":1748390400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"EPSRC Centre of Doctoral Training in Distributed Algorithms","award":["EP\/S023445\/1"],"award-info":[{"award-number":["EP\/S023445\/1"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Math Imaging Vis"],"published-print":{"date-parts":[[2025,6]]},"abstract":"Abstract<\/jats:title>\n In this paper, we address the maximum cover problem of a rotating field of view (FOV) with a convex polygon \n \n $$\\mathcal {P}$$<\/jats:tex-math>\n \n P<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> with n<\/jats:italic> vertices. The problem is defined as determining the optimal rotation angle \n \n $$\\theta $$<\/jats:tex-math>\n \n \u03b8<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> of the FOV, characterised by a fixed centre and inner angle \n \n $$\\phi $$<\/jats:tex-math>\n \n \u03d5<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, such that the intersection between the FOV and \n \n $$\\mathcal {P}$$<\/jats:tex-math>\n \n P<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> has the maximum possible area. This problem is relevant for applications in visibility optimisation and uncertainty reduction in localisation tasks. We present a theoretical framework and a corresponding algorithm to approximate the value of the maximum, ensuring that the solution is close to the optimal within the specified precision. The intersection between the rotating FOV and \n \n $$\\mathcal {P}$$<\/jats:tex-math>\n \n P<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> forms a convex polygon whose number of vertices varies with the rotation angle \n \n $$\\theta $$<\/jats:tex-math>\n \n \u03b8<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. We analytically derive the area of the intersection when it takes its simplest form, a quadrilateral, as a two-variable function \n \n $$A(\\theta ,\\phi )$$<\/jats:tex-math>\n \n \n A<\/mml:mi>\n (<\/mml:mo>\n \u03b8<\/mml:mi>\n ,<\/mml:mo>\n \u03d5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. The function \n \n $$A(\\theta ,\\phi )$$<\/jats:tex-math>\n \n \n A<\/mml:mi>\n (<\/mml:mo>\n \u03b8<\/mml:mi>\n ,<\/mml:mo>\n \u03d5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, with the angle of rotation \n \n $$\\theta $$<\/jats:tex-math>\n \n \u03b8<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and the fixed inner angle \n \n $$\\phi $$<\/jats:tex-math>\n \n \u03d5<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, denoted as \n \n $$A_{\\phi }(\\theta )$$<\/jats:tex-math>\n \n \n \n A<\/mml:mi>\n \u03d5<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n \u03b8<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, is non-monotonic and has multiple local extreme points inside of a given domain which poses a challenge in identifying them and approximating the global maximum. We found an alternative way to express it by various compositions of a function \n \n $$A_{\\theta }(\\phi )$$<\/jats:tex-math>\n \n \n \n A<\/mml:mi>\n \u03b8<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n \u03d5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> (with a restricted inner angle \n \n $$\\phi $$<\/jats:tex-math>\n \n \u03d5<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and a fixed direction \n \n $$\\theta $$<\/jats:tex-math>\n \n \u03b8<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>). We show that \n \n $$A_{\\theta }(\\phi )$$<\/jats:tex-math>\n \n \n \n A<\/mml:mi>\n \u03b8<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n \u03d5<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> has an analytical solution in the special case of a two-sector intersection and later provides a constrictive solution for the original problem. We develop an algorithm that approximates the direction of the field of view, with precision \n \n $$\\varepsilon >1$$<\/jats:tex-math>\n \n \n \u03b5<\/mml:mi>\n ><\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, and complexity \n \n $$\\mathcal {O}(n(\\log {n}+(\\log {\\varepsilon })\/\\phi ))$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n +<\/mml:mo>\n (<\/mml:mo>\n log<\/mml:mo>\n \u03b5<\/mml:mi>\n )<\/mml:mo>\n \/<\/mml:mo>\n \u03d5<\/mml:mi>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>.\n<\/jats:p>","DOI":"10.1007\/s10851-025-01250-0","type":"journal-article","created":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T07:35:51Z","timestamp":1748417751000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Maximum Cover with Rotating Field of View"],"prefix":"10.1007","volume":"67","author":[{"given":"Igor","family":"Potapov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jason F.","family":"Ralph","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Theofilos","family":"Triommatis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,28]]},"reference":[{"key":"1250_CR1","doi-asserted-by":"crossref","unstructured":"Abrahamsen, M.: Covering polygons is even harder. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 375\u2013386, (2022)","DOI":"10.1109\/FOCS52979.2021.00045"},{"key":"1250_CR2","doi-asserted-by":"crossref","unstructured":"Abrahamsen, M., Adamaszek, A., Miltzow, T.: The art gallery problem is $$\\exists \\mathbb{R} $$-complete. J. ACM, 69(1), (2021)","DOI":"10.1145\/3486220"},{"issue":"3","key":"1250_CR3","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1007\/s00224-018-9885-y","volume":"63","author":"C Alegr\u00eda-Galicia","year":"2019","unstructured":"Alegr\u00eda-Galicia, C., Orden, D., Palios, L., Seara, C., Urrutia, J.: Capturing points with a rotating polygon (and a 3d extension). Theory Comput. Syst. 63(3), 543\u2013566 (2019)","journal-title":"Theory Comput. Syst."},{"key":"1250_CR4","volume-title":"Convergence and Applications of Newton-type Iterations","author":"IK Argyros","year":"2008","unstructured":"Argyros, I.K.: Convergence and Applications of Newton-type Iterations. Springer, Berlin (2008)"},{"issue":"1","key":"1250_CR5","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF01840436","volume":"1","author":"T Asano","year":"1986","unstructured":"Asano, T., Guibas, L., Hershberger, J., Imai, H.: Visibility of disjoint polygons. Algorithmica 1(1), 49\u201363 (1986)","journal-title":"Algorithmica"},{"issue":"3, Part A","key":"1250_CR6","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/j.comgeo.2013.10.003","volume":"47","author":"G Barequet","year":"2014","unstructured":"Barequet, G., Goryachev, A.: Offset polygon and annulus placement problems. Comput. Geom. 47(3, Part A), 407\u2013434 (2014)","journal-title":"Comput. Geom."},{"issue":"3","key":"1250_CR7","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0925-7721(01)00070-0","volume":"23","author":"P Bose","year":"2002","unstructured":"Bose, P., Lubiw, A., Munro, J.: Efficient visibility queries in simple polygons. Comput. Geom. 23(3), 313\u2013335 (2002)","journal-title":"Comput. Geom."},{"issue":"4","key":"1250_CR8","doi-asserted-by":"publisher","first-page":"860","DOI":"10.1007\/s00454-016-9785-3","volume":"56","author":"TM Chan","year":"2016","unstructured":"Chan, T.M.: A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions. Discret. Comput. Geom. 56(4), 860\u2013865 (2016)","journal-title":"Discret. Comput. Geom."},{"issue":"4","key":"1250_CR9","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/s00454-007-1328-5","volume":"37","author":"O Cheong","year":"2007","unstructured":"Cheong, O., Efrat, A., Har-Peled, S.: Finding a guard that sees most and a shop that sells most. Discrete Comput. Geom. 37(4), 545\u2013563 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"1250_CR10","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.ic.2013.02.001","volume":"225","author":"J Czyzowicz","year":"2013","unstructured":"Czyzowicz, J., Ilcinkas, D., Labourel, A., Pelc, A.: Worst-case optimal exploration of terrains with obstacles. Inform. Comput. 225, 16\u201328 (2013)","journal-title":"Inform. Comput."},{"issue":"5","key":"1250_CR11","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/PL00005845","volume":"31","author":"M de Berg","year":"1998","unstructured":"de Berg, M., Cheong, O., Devillers, O., van Kreveld, M., Teillaud, M.: Computing the maximum overlap of two convex polygons under translations. Theory Comput. Syst. 31(5), 613\u2013628 (1998)","journal-title":"Theory Comput. Syst."},{"key":"1250_CR12","doi-asserted-by":"crossref","unstructured":"Engquist, B. (ed.): Encyclopedia of Applied and Computational Mathematics. Springer (2015)","DOI":"10.1007\/978-3-540-70529-1"},{"key":"1250_CR13","doi-asserted-by":"crossref","unstructured":"Erdem, U.M., Sclaroff, S.: Automated camera layout to satisfy task-specific and floor plan-specific coverage requirements. Computer Vision and Image Understanding 103(3), 156\u2013169 (2006). (Special issue on Omnidirectional Vision and Camera NetworksSpecial issue on Omnidirectional Vision and Camera Networks)","DOI":"10.1016\/j.cviu.2006.06.005"},{"key":"1250_CR14","doi-asserted-by":"crossref","unstructured":"Floriani, L., Magillo, P.: Algorithms for visibility computation on terrains: A survey. Environ. Planning B Planning Des. 30(5), 709\u2013728 (2003)","DOI":"10.1068\/b12979"},{"key":"1250_CR15","volume-title":"A First Course in Abstract Algebra","author":"JB Fraleigh","year":"2003","unstructured":"Fraleigh, J.B.: A First Course in Abstract Algebra. Pearson Education India, Noida (2003)"},{"issue":"12","key":"1250_CR16","doi-asserted-by":"publisher","first-page":"2767","DOI":"10.1109\/LWC.2021.3116561","volume":"10","author":"V Gadiraju","year":"2021","unstructured":"Gadiraju, V., Wu, H.-C., Busch, C., Neupane, P., Chang, S.Y., Huang, S.C.-H.: Novel sensor\/access-point coverage-area maximization for arbitrary indoor polygonal geometries. IEEE Wireless Commun. Lett. 10(12), 2767\u20132771 (2021)","journal-title":"IEEE Wireless Commun. Lett."},{"issue":"1","key":"1250_CR17","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/s00453-016-0152-9","volume":"78","author":"S Har-Peled","year":"2017","unstructured":"Har-Peled, S., Roy, S.: Approximating the maximum overlap of polygons under translation. Algorithmica 78(1), 147\u2013165 (2017)","journal-title":"Algorithmica"},{"key":"1250_CR18","doi-asserted-by":"crossref","unstructured":"Lax, P.D.: The quotient of exponential polynomials. Duke Math. J. 15(4), 967\u2013970 (1948)","DOI":"10.1215\/S0012-7094-48-01586-5"},{"key":"1250_CR19","doi-asserted-by":"publisher","first-page":"631","DOI":"10.5951\/mathteacher.110.8.0631","volume":"110","author":"W Lim","year":"2017","unstructured":"Lim, W.: Shoelace formula: Connecting the area of a polygon and vector cross product. Math. Teacher 110, 631\u2013636 (2017)","journal-title":"Math. Teacher"},{"key":"1250_CR20","doi-asserted-by":"crossref","unstructured":"Marengoni, B.D.M., Hanson, A., Sitaraman, R.: A system to place observers on a polyhedral terrain in polynomial time. Image Vis. Comput. 18(10), 773\u2013780 (2000)","DOI":"10.1016\/S0262-8856(99)00045-1"},{"key":"1250_CR21","doi-asserted-by":"crossref","unstructured":"Mohd\u00a0Yusoff, S. K., Md\u00a0Said, A., Ismail, I.: Optimal camera placement for 3d environment. In J.\u00a0M. Zain, W.\u00a0M.\u00a0b. Wan\u00a0Mohd, and E.\u00a0El-Qawasmeh, editors, Software Engineering and Computer Systems, pages 448\u2013459, Berlin, Heidelberg, (2011). Springer Berlin Heidelberg","DOI":"10.1007\/978-3-642-22191-0_39"},{"key":"1250_CR22","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-030-58150-3_25","volume-title":"Computing and Combinatorics","author":"BJ Nilsson","year":"2020","unstructured":"Nilsson, B.J., Orden, D., Palios, L., Seara, C., \u017byli\u0144ski, P.: Shortest watchman tours in simple polygons under rotated monotone visibility. In: Kim, D., Uma, R.N., Cai, Z., Lee, D.H. (eds.) Computing and Combinatorics, pp. 311\u2013323. Springer International Publishing, Cham (2020)"},{"key":"1250_CR23","doi-asserted-by":"crossref","unstructured":"Polyak, R.A.: Introduction to continuous optimization \/ Roman A. Polyak. Springer optimization and its applications ; 172. Springer, Cham, Switzerland, (2021)","DOI":"10.1007\/978-3-030-68713-7"},{"key":"1250_CR24","unstructured":"Spivak, M.: Calculus. Revert\u00e9, (2019)"},{"key":"1250_CR25","doi-asserted-by":"crossref","unstructured":"Triommatis, T., Potapov, I., Rees, G., Ralph, J.F.: A geometric approach to passive localisation. In: 2022 25th International Conference on Information Fusion (FUSION), pp 1\u20138, (2022)","DOI":"10.23919\/FUSION49751.2022.9841395"}],"container-title":["Journal of Mathematical Imaging and Vision"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10851-025-01250-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10851-025-01250-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10851-025-01250-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T09:44:29Z","timestamp":1751535869000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10851-025-01250-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,28]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["1250"],"URL":"https:\/\/doi.org\/10.1007\/s10851-025-01250-0","relation":{},"ISSN":["0924-9907","1573-7683"],"issn-type":[{"type":"print","value":"0924-9907"},{"type":"electronic","value":"1573-7683"}],"subject":[],"published":{"date-parts":[[2025,5,28]]},"assertion":[{"value":"5 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2025","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 conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"33"}}