论文标题
1.5D地形中的$ k $ gons
Large $k$-gons in a 1.5D Terrain
论文作者
论文摘要
给定的是1.5D地形$ \ MATHCAL {T} $，即$ x $ - 单酮多边形链中的$ \ Mathbb {r}^2 $。对于给定的$ 2 \ le K \ le n $，我们的目标是近似于$ \ Mathcal {t} $内部的最大面积或周长凸多边形。对于常量的$ k> 3 $，我们设计了一个fptas，该FPTA有效地近似于最大的凸多边形，其中最多是$ k $顶点，在因子$（1-ε）$之内。对于$ k = 2 $的情况，我们设计了一个$ o（n）$ time精确算法，用于计算$ \ mathcal {t} $中的最长行段，对于$ k = 3 $，我们设计了一个$ o（n \ log n）$ time精确算法，以计算最大的perimeter triangle，以计算最大的perimeter Triangle，以计算$ \ \ Mather的$ \ Mather}。
Given is a 1.5D terrain $\mathcal{T}$, i.e., an $x$-monotone polygonal chain in $\mathbb{R}^2$. For a given $2\le k\le n$, our objective is to approximate the largest area or perimeter convex polygon of exactly or at most $k$ vertices inside $\mathcal{T}$. For a constant $k>3$, we design an FPTAS that efficiently approximates the largest convex polygons with at most $k$ vertices, within a factor $(1-ε)$. For the case where $k=2$, we design an $O(n)$ time exact algorithm for computing the longest line segment in $\mathcal{T}$, and for $k=3$, we design an $O(n \log n)$ time exact algorithm for computing the largest-perimeter triangle that lies within $\mathcal{T}$.
