**Reference**:- Greg Aloupis, Prosenjit Bose, Erik D. Demaine, Stefan Langerman, Henk Meijer, Mark Overmars, and Godfried T. Toussaint, “Computing Signed Permutations of Polygons”, in
*Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002)*, Lethbridge, Alberta, Canada, August 12–14, 2002. **Abstract**:-
Given a planar polygon (or chain) with a list of edges
{
*e*_{1},*e*_{2},*e*_{3}, …,*e*_{n-1},*e*_{n}}, 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. Using these permuting operations, we explore the complexity of performing certain actions, such as convexifying a given polygon or obtaining its mirror image. 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. The complexity of some problems varies depending on whether a polygon is signed or unsigned. An additional restriction in many cases is that polygons remain simple after every permutation. **Comments**:- A short version of the paper appeared on pages 68-71.
Both the short and long versions are available from the electronic proceedings as http://www.cs.uleth.ca/~wismath/cccg/papers/23l.ps (long version) and http://www.cs.uleth.ca/~wismath/cccg/papers/23m.ps (short version).

**Length**:- The paper is 14 pages.
**Availability**:- The paper is available in PostScript (338k) and gzipped PostScript (112k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated February 26, 2024 by Erik Demaine.