The Maximum Cover with Rotating Field of View

Abstract In this paper, we address the maximum cover problem of a rotating field of view (FOV) with a convex polygon $$\mathcal {P}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>P</mml:mi> </mml:math> with n vertices. The problem is defined as determining the optimal rotation angle $$\theta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>θ</mml:mi> </mml:math> of the FOV, characterised by a fixed centre and inner angle $$\phi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ϕ</mml:mi> </mml:math> , such that the intersection between the FOV and $$\mathcal {P}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>P</mml:mi> </mml:math> 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 $$\mathcal {P}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>P</mml:mi> </mml:math> forms a convex polygon whose number of vertices varies with the rotation angle $$\theta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>θ</mml:mi> </mml:math> . We analytically derive the area of the intersection when it takes its simplest form, a quadrilateral, as a two-variable function $$A(\theta ,\phi )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>(</mml:mo> <mml:mi>θ</mml:mi> <mml:mo>,</mml:mo> <mml:mi>ϕ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . The function $$A(\theta ,\phi )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>(</mml:mo> <mml:mi>θ</mml:mi> <mml:mo>,</mml:mo> <mml:mi>ϕ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , with the angle of rotation $$\theta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>θ</mml:mi> </mml:math> and the fixed inner angle $$\phi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ϕ</mml:mi> </mml:math> , denoted as $$A_{\phi }(\theta )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>A</mml:mi> <mml:mi>ϕ</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>θ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , 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 $$A_{\theta }(\phi )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>A</mml:mi> <mml:mi>θ</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>ϕ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> (with a restricted inner angle $$\phi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ϕ</mml:mi> </mml:math> and a fixed direction $$\theta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>θ</mml:mi> </mml:math> ). We show that $$A_{\theta }(\phi )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>A</mml:mi> <mml:mi>θ</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>ϕ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> 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 $$\varepsilon &gt;1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ε</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , and complexity $$\mathcal {O}(n(\log {n}+(\log {\varepsilon })/\phi ))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>ε</mml:mi> <mml:mo>)</mml:mo> <mml:mo>/</mml:mo> <mml:mi>ϕ</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> .