Computing Signed Permutations of Polygon
Given a planar polygon (or chain) with a list of edges {e[subscript 1], e[subscript 2], e[subscript 3], …, e[subscript n-1], e[subscript 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...
| Main Authors: | , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
World Scientific
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73973 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826253198758772736 |
|---|---|
| author | Aloupis, Greg Bose, Prosenjit Demaine, Erik D. Langerman, Stefan Meijer, Henk Overmars, Mark Toussaint, Godfried T. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Aloupis, Greg Bose, Prosenjit Demaine, Erik D. Langerman, Stefan Meijer, Henk Overmars, Mark Toussaint, Godfried T. |
| author_sort | Aloupis, Greg |
| collection | MIT |
| description | Given a planar polygon (or chain) with a list of edges {e[subscript 1], e[subscript 2], e[subscript 3], …, e[subscript n-1], e[subscript 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. 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(n[superscript 2]) 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. |
| first_indexed | 2024-09-23T16:37:56Z |
| format | Article |
| id | mit-1721.1/73973 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:37:56Z |
| publishDate | 2012 |
| publisher | World Scientific |
| record_format | dspace |
| spelling | mit-1721.1/739732022-10-02T08:33:56Z Computing Signed Permutations of Polygon Aloupis, Greg Bose, Prosenjit Demaine, Erik D. Langerman, Stefan Meijer, Henk Overmars, Mark Toussaint, Godfried T. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Given a planar polygon (or chain) with a list of edges {e[subscript 1], e[subscript 2], e[subscript 3], …, e[subscript n-1], e[subscript 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. 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(n[superscript 2]) 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. 2012-10-15T16:31:23Z 2012-10-15T16:31:23Z 2011 2010-01 Article http://purl.org/eprint/type/JournalArticle 0218-1959 http://hdl.handle.net/1721.1/73973 Aloupis, Greg et al. “Computing Signed Permutations of Polygon.” International Journal of Computational Geometry & Applications 21.01 (2011): 87–100. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1142/s0218195911003561 International Journal of Computational Geometry & Applications Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf World Scientific Other University Web Domain |
| spellingShingle | Aloupis, Greg Bose, Prosenjit Demaine, Erik D. Langerman, Stefan Meijer, Henk Overmars, Mark Toussaint, Godfried T. Computing Signed Permutations of Polygon |
| title | Computing Signed Permutations of Polygon |
| title_full | Computing Signed Permutations of Polygon |
| title_fullStr | Computing Signed Permutations of Polygon |
| title_full_unstemmed | Computing Signed Permutations of Polygon |
| title_short | Computing Signed Permutations of Polygon |
| title_sort | computing signed permutations of polygon |
| url | http://hdl.handle.net/1721.1/73973 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT aloupisgreg computingsignedpermutationsofpolygon AT boseprosenjit computingsignedpermutationsofpolygon AT demaineerikd computingsignedpermutationsofpolygon AT langermanstefan computingsignedpermutationsofpolygon AT meijerhenk computingsignedpermutationsofpolygon AT overmarsmark computingsignedpermutationsofpolygon AT toussaintgodfriedt computingsignedpermutationsofpolygon |