Home | Issues | About JGAA | Instructions for Authors |
Special issue on Selected papers from the Twenty-eighth International Symposium on Graph Drawing and Network Visualization, GD 2020
DOI: 10.7155/jgaa.00599
Polygons with Prescribed Angles in 2D and 3D
Vol. 26, no. 3, pp. 363-380, 2022. Regular paper.
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,\ldots, \alpha_{n-1})$, $\alpha_i\in (-\pi,\pi)$,
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 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.
This work is licensed under the terms of the CC-BY license.
|
Submitted: October 2020.
Reviewed: April 2022.
Revised: April 2022.
Accepted: May 2022.
Final: May 2022.
Published: June 2022.
|
Journal Supporters
|