Paper by Erik D. Demaine

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.

BibTeX

@InProceedings{PermutingPolygons_CCCG2002,
  AUTHOR        = {Greg Aloupis and Prosenjit Bose and Erik D. Demaine and
                   Stefan Langerman and Henk Meijer and Mark Overmars and
                   Godfried T. Toussaint},
  TITLE         = {Computing Signed Permutations of Polygons},
  BOOKTITLE     = {Proceedings of the 14th Canadian Conference on Computational
                   Geometry (CCCG 2002)},
  bookurl       = {http://www.cs.uleth.ca/cccg},
  ADDRESS       = {Lethbridge, Alberta, Canada},
  MONTH         = {August 12--14},
  YEAR          = 2002,

  LENGTH        = {14 pages},
  dblp          = {https://dblp.org/rec/conf/cccg/AloupisBDLMOT02},
  COMMENTS      = {A <A HREF="short.ps">short version of the paper</A> appeared
                   on pages 68-71.
                   <P>
                   Both the short and long versions are available from the
                   <A HREF="http://www.cs.uleth.ca/~wismath/cccg/proceedings/">
                   electronic proceedings</A> as
                   <A HREF="http://www.cs.uleth.ca/~wismath/cccg/papers/23l.ps">http://www.cs.uleth.ca/~wismath/cccg/papers/23l.ps</A>
                   (long version) and
                   <A HREF="http://www.cs.uleth.ca/~wismath/cccg/papers/23m.ps">http://www.cs.uleth.ca/~wismath/cccg/papers/23m.ps</A>
                   (short version), and from <A HREF="https://doi.org/10.1142/S0218195911003561">World Scientific</A>.},
  unrefereed    = 1,
  ee            = {http://www.cs.uleth.ca/~wismath/cccg/papers/23l.ps},
  papers        = {PermutingPolygons_CGTA; PermutingPolygons_IJCGA},
}

Abstract:

Given a planar polygon (or chain) with a list of edges {e₁, e₂, e₃, …, 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), and from World Scientific.

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]

Related papers:

PermutingPolygons_IJCGA (Computing Signed Permutations of Polygons)