Paper by Erik D. Demaine

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.

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. 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.

A short version of the paper appeared on pages 68-71.

Both the short and long versions are available from the electronic proceedings as (long version) and (short version).

The paper is 14 pages.

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.
These pages are generated automagically from a BibTeX file.
Last updated June 13, 2024 by Erik Demaine.