Polygons with Prescribed Angles in 2D and 3D

Abstract

We consider the construction of a polygon $P$ with $n$ vertices whose turning angles at the vertices are given by a sequence $A=({\alpha }_0,\dots ,{\alpha }_{n-1})$, ${\alpha }_i\in (-\pi ,\pi )$, for $i\in \{0,\dots ,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.

15 pages, 9 figures, a new section about self-intersecting realizations in 3D