|国家预印本平台
首页|Line Aspect Ratio

Line Aspect Ratio

Line Aspect Ratio

来源:Arxiv_logoArxiv
英文摘要

We address the problem of covering a target segment $\overline{uv}$ using a finite set of guards $\mathcal{S}$ placed on a source segment $\overline{xy}$ within a simple polygon $\mathcal{P}$, assuming weak visibility between the target and source. Without geometric constraints, $\mathcal{S}$ may be infinite, as shown by prior hardness results. To overcome this, we introduce the {\it line aspect ratio} (AR), defined as the ratio of the \emph{long width} (LW) to the \emph{short width} (SW) of $\mathcal{P}$. These widths are determined by parallel lines tangent to convex vertices outside $\mathcal{P}$ (LW) and reflex vertices inside $\mathcal{P}$ (SW), respectively. Under the assumption that AR is constant or polynomial in $n$ (the polygon's complexity), we prove that a finite guard set $\mathcal{S}$ always exists, with size bounded by $\mathcal{O}(\text{AR})$. This AR-based framework generalizes some previous assumptions, encompassing a broader class of polygons. Our result establishes a framework guaranteeing finite solutions for segment guarding under practical and intuitive geometric constraints.

Arash Vaezi

数学

Arash Vaezi.Line Aspect Ratio[EB/OL].(2025-06-25)[2025-07-16].https://arxiv.org/abs/2506.20508.点此复制

评论