## Abstract

We consider the construction of a polygon P with n vertices whose turning angles at the vertices are given by a sequence A = (α_{0}, …, α_{n−1}), α_{i} ∈ (−π, π), for i ∈ {0, …, 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 ⊂ R^{2} realizing A has at least c crossings, for every c ∈ N, and describe an efficient algorithm that constructs, for a given sequence A, a generic polygon P ⊂ 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 ⊂ R^{3}, and for every realizable sequence the algorithm finds a realization.

Original language | English (US) |
---|---|

Pages (from-to) | 363-380 |

Number of pages | 18 |

Journal | Journal of Graph Algorithms and Applications |

Volume | 26 |

Issue number | 3 |

DOIs | |

State | Published - 2022 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science
- Computer Science Applications
- Geometry and Topology
- Computational Theory and Mathematics