<p>In this paper, we address the maximum cover problem of a rotating field of view (FOV) with a convex polygon <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10851_2025_1250_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {P}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">P</mi> </math></EquationSource> </InlineEquation> with <i>n</i> vertices. The problem is defined as determining the optimal rotation angle <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10851_2025_1250_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(\theta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>θ</mi> </math></EquationSource> </InlineEquation> of the FOV, characterised by a fixed centre and inner angle <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10851_2025_1250_Article_IEq3.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="16" /> </InlineMediaObject> <EquationSource Format="TEX">\(\phi \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϕ</mi> </math></EquationSource> </InlineEquation>, such that the intersection between the FOV and <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10851_2025_1250_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {P}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">P</mi> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10851_2025_1250_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {P}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">P</mi> </math></EquationSource> </InlineEquation> forms a convex polygon whose number of vertices varies with the rotation angle <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10851_2025_1250_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(\theta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>θ</mi> </math></EquationSource> </InlineEquation>. We analytically derive the area of the intersection when it takes its simplest form, a quadrilateral, as a two-variable function <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10851_2025_1250_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="52" /> </InlineMediaObject> <EquationSource Format="TEX">\(A(\theta ,\phi )\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>A</mi> <mo stretchy="false">(</mo> <mi>θ</mi> <mo>,</mo> <mi>ϕ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. The function <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10851_2025_1250_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="52" /> </InlineMediaObject> <EquationSource Format="TEX">\(A(\theta ,\phi )\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>A</mi> <mo stretchy="false">(</mo> <mi>θ</mi> <mo>,</mo> <mi>ϕ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, with the angle of rotation <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10851_2025_1250_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(\theta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>θ</mi> </math></EquationSource> </InlineEquation> and the fixed inner angle <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10851_2025_1250_Article_IEq3.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="16" /> </InlineMediaObject> <EquationSource Format="TEX">\(\phi \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϕ</mi> </math></EquationSource> </InlineEquation>, denoted as <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10851_2025_1250_Article_IEq11.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">\(A_{\phi }(\theta )\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>A</mi> <mi>ϕ</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>θ</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10851_2025_1250_Article_IEq12.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">\(A_{\theta }(\phi )\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>A</mi> <mi>θ</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>ϕ</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> (with a restricted inner angle <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10851_2025_1250_Article_IEq3.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="16" /> </InlineMediaObject> <EquationSource Format="TEX">\(\phi \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϕ</mi> </math></EquationSource> </InlineEquation> and a fixed direction <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10851_2025_1250_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(\theta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>θ</mi> </math></EquationSource> </InlineEquation>). We show that <InlineEquation ID="IEq15"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10851_2025_1250_Article_IEq12.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">\(A_{\theta }(\phi )\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>A</mi> <mi>θ</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>ϕ</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq16"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10851_2025_1250_Article_IEq16.gif" Format="GIF" Height="13" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">\(\varepsilon &gt;1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ε</mi> <mo>&gt;</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, and complexity <InlineEquation ID="IEq17"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10851_2025_1250_Article_IEq17.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="165" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {O}(n(\log {n}+(\log {\varepsilon })/\phi ))\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>n</mi> <mo>+</mo> <mo stretchy="false">(</mo> <mo>log</mo> <mi>ε</mi> <mo stretchy="false">)</mo> <mo stretchy="false">/</mo> <mi>ϕ</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

The Maximum Cover with Rotating Field of View

  • Igor Potapov,
  • Jason F. Ralph,
  • Theofilos Triommatis

摘要

In this paper, we address the maximum cover problem of a rotating field of view (FOV) with a convex polygon \(\mathcal {P}\) P with n vertices. The problem is defined as determining the optimal rotation angle \(\theta \) θ of the FOV, characterised by a fixed centre and inner angle \(\phi \) ϕ , such that the intersection between the FOV and \(\mathcal {P}\) P 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}\) P forms a convex polygon whose number of vertices varies with the rotation angle \(\theta \) θ . We analytically derive the area of the intersection when it takes its simplest form, a quadrilateral, as a two-variable function \(A(\theta ,\phi )\) A ( θ , ϕ ) . The function \(A(\theta ,\phi )\) A ( θ , ϕ ) , with the angle of rotation \(\theta \) θ and the fixed inner angle \(\phi \) ϕ , denoted as \(A_{\phi }(\theta )\) A ϕ ( θ ) , 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 )\) A θ ( ϕ ) (with a restricted inner angle \(\phi \) ϕ and a fixed direction \(\theta \) θ ). We show that \(A_{\theta }(\phi )\) A θ ( ϕ ) 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 >1\) ε > 1 , and complexity \(\mathcal {O}(n(\log {n}+(\log {\varepsilon })/\phi ))\) O ( n ( log n + ( log ε ) / ϕ ) ) .