Polygons with Prescribed Angles in 2D and 3D

Alon Efrat, Radoslav Fulek, Stephen Kobourov, Csaba D. Tóth

Research output: Contribution to journalArticlepeer-review

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 ⊂ R2 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 ⊂ R2 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 ⊂ R3, and for every realizable sequence the algorithm finds a realization.

Original languageEnglish (US)
Pages (from-to)363-380
Number of pages18
JournalJournal of Graph Algorithms and Applications
Volume26
Issue number3
DOIs
StatePublished - 2022

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'Polygons with Prescribed Angles in 2D and 3D'. Together they form a unique fingerprint.

Cite this