We explore an extension to rectilinear convexity of the classic problem of computing the convex hull of a set of geometric objects. Namely, we solve the problem of computing the rectilinear convex hull with arbitrary orientation for a set of segments and circles. We describe efficient algorithms to compute and maintain the objects appearing on the boundary of the rectilinear convex hull of such sets, while we rotate the coordinate axes by an angle that goes from 0 to <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10898_2025_1482_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">$2\pi $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi>π</mi> </mrow> </math></EquationSource> </InlineEquation>. We first consider a set of n segments. If the segments are not necessarily disjoint, we describe an algorithm that runs in optimal <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10898_2025_1482_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="72" /> </InlineMediaObject> <EquationSource Format="TEX">$\Theta (n\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time and <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10898_2025_1482_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="70" /> </InlineMediaObject> <EquationSource Format="TEX">$O(n\alpha (n))$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>α</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> space, where <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10898_2025_1482_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="35" /> </InlineMediaObject> <EquationSource Format="TEX">$\alpha (n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is the extremely slowly growing inverse of Ackermann’s function. If instead the segments form a simple polygonal chain, we describe an algorithm that improves the previous space complexity to <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10898_2025_1482_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="36" /> </InlineMediaObject> <EquationSource Format="TEX">$\Theta (n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. We then extend the techniques used in these algorithms to a set of n circles. The resulting algorithm runs in optimal <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10898_2025_1482_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="72" /> </InlineMediaObject> <EquationSource Format="TEX">$\Theta (n\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time and <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10898_2025_1482_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="36" /> </InlineMediaObject> <EquationSource Format="TEX">$\Theta (n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> space.

Time-optimal computation of the rectilinear convex hull with arbitrary orientation of sets of segments and circles

期刊论文
出版模式：

开放获取
发表日期：

2025年3月26日

查看全文

Carlos Alegría,
Justin Dallant,
Pablo Pérez-Lantero,
Carlos Seara

摘要

We explore an extension to rectilinear convexity of the classic problem of computing the convex hull of a set of geometric objects. Namely, we solve the problem of computing the rectilinear convex hull with arbitrary orientation for a set of segments and circles. We describe efficient algorithms to compute and maintain the objects appearing on the boundary of the rectilinear convex hull of such sets, while we rotate the coordinate axes by an angle that goes from 0 to $2\pi $ $2 π$ . We first consider a set of n segments. If the segments are not necessarily disjoint, we describe an algorithm that runs in optimal $\Theta (n\log n)$ $Θ (n log n)$ time and $O(n\alpha (n))$ $O (n α (n))$ space, where $\alpha (n)$ $α (n)$ is the extremely slowly growing inverse of Ackermann’s function. If instead the segments form a simple polygonal chain, we describe an algorithm that improves the previous space complexity to $\Theta (n)$ $Θ (n)$ . We then extend the techniques used in these algorithms to a set of n circles. The resulting algorithm runs in optimal $\Theta (n\log n)$ $Θ (n log n)$ time and $\Theta (n)$ $Θ (n)$ space.