论文标题
多边形在2D和3D中有规定的角度
Polygons with Prescribed Angles in 2D and 3D
论文作者
论文摘要
我们考虑使用$ n $顶点的多边形$ p $构造，其顶点的角度由序列$ a =（α_0，\ ldots，α__{n-1}）$，$α_i\ in（-π，π）$，对于$ i \ in \ in \ in \ in \ {0，\ ldots，n-ldots，n-n-1-1-1 $多边形实现$ a $的问题可以看作是在顶点构建具有规定角度的图形的直线图，因此，这是构建\ emph {angle graph}的精心研究问题的一种特殊情况。 在2D中，我们表征了序列$ a $的每个通用多边形$ p \ subset \ mathbb {r}^2 $实现$ a $至少具有$ c $ crossings，每个$ c \ in \ in \ mathbb {n} $中的每个$ c \ in \ mathbb {n} $，并描述了一个有效的算法，该算法是构建的，对于给定序列$ a $ a $ a $ a $ a $ a $ a pp pol pp po pol pp po pol pp po p p p p p p p p p plegon $ a \ Mathbb {r}^2 $，实现了$ a $，并具有最小的交叉数。 在3D中，我们描述了一种有效的算法，该算法测试是否可以通过（不一定是通用的）Polygon $ P \ subset \ Mathbb {r}^3 $实现给定序列$ a $，并且对于每个可实现的序列，算法都可以找到实现。
We consider the construction of a polygon $P$ with $n$ vertices whose turning angles at the vertices are given by a sequence $A=(α_0,\ldots, α_{n-1})$, $α_i\in (-π,π)$, for $i\in\{0,\ldots, n-1\}$. The problem of realizing $A$ by a polygon can be seen as that of constructing a straight-line drawing of a graph with prescribed angles at vertices, and hence, it is a special case of the well studied problem of constructing an \emph{angle graph}. In 2D, we characterize sequences $A$ for which every generic polygon $P\subset \mathbb{R}^2$ realizing $A$ has at least $c$ crossings, for every $c\in \mathbb{N}$, and describe an efficient algorithm that constructs, for a given sequence $A$, a generic polygon $P\subset \mathbb{R}^2$ that realizes $A$ with the minimum number of crossings. In 3D, we describe an efficient algorithm that tests whether a given sequence $A$ can be realized by a (not necessarily generic) polygon $P\subset \mathbb{R}^3$, and for every realizable sequence the algorithm finds a realization.
