Computing signed permutations of polygons

Greg Aloupis, Prosenjit Bose, Erik D. Demaine, Stefan Langerman, Henk Meijer, Mark Overmars, Godfried T. Toussaint

Research output: Contribution to journalArticlepeer-review

Abstract

Given a planar polygon (or chain) with a list of edges {e1, e2, e3, ..., en-1, en}, we examine the effect of several operations that permute this edge list, resulting in the formation of a new polygon. The main operations that we consider are: reversals which involve inverting the order of a sublist, transpositions which involve interchanging subchains (sublists), and edge-swaps which are a special case and involve interchanging two consecutive edges. When each edge of the given polygon has also been assigned a direction we say that the polygon is signed. In this case any edge involved in a reversal changes direction. We show that a star-shaped polygon can be convexified using O(n2) edge-swaps, while maintaining simplicity, and that this is tight in the worst case. We show that determining whether a signed polygon P can be transformed to one that has rotational or mirror symmetry with P, using transpositions, takes Θ(n log n) time. We prove that the problem of deciding whether transpositions can modify a polygon to fit inside a rectangle is weakly NP-complete. Finally we give an O(n log n) time algorithm to compute the maximum endpoint distance for an oriented chain.

Original languageEnglish (US)
Pages (from-to)87-100
Number of pages14
JournalInternational Journal of Computational Geometry and Applications
Volume21
Issue number1
DOIs
StatePublished - Feb 2011

Keywords

  • Computational geometry
  • geometric permutation
  • polygonal reconfiguration

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Computing signed permutations of polygons'. Together they form a unique fingerprint.

Cite this