License: 
Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1345
URN: urn:nbn:de:0030-drops-13457
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1345/
Damian, Mirela ;
Flatland, Robin ;
O'Rourke, Joseph ;
Ramaswani, Suneeta
Connecting Polygonizations via Stretches and Twangs
Abstract
We show that the space of polygonizations of a fixed planar point
set $S$ of $n$ points is connected by $O(n^2)$ ``moves'' between
simple polygons. Each move is composed of a sequence of atomic
moves called ``stretches'' and ``twangs''. These atomic moves walk
between weakly simple ``polygonal wraps'' of $S$. These moves show
promise to serve as a basis for generating random polygons.
BibTeX - Entry
@InProceedings{damian_et_al:LIPIcs:2008:1345,
author = {Mirela Damian and Robin Flatland and Joseph O'Rourke and Suneeta Ramaswani},
title = {{Connecting Polygonizations via Stretches and Twangs}},
booktitle = {25th International Symposium on Theoretical Aspects of Computer Science},
pages = {217--228},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-06-4},
ISSN = {1868-8969},
year = {2008},
volume = {1},
editor = {Susanne Albers and Pascal Weil},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1345},
URN = {urn:nbn:de:0030-drops-13457},
doi = {10.4230/LIPIcs.STACS.2008.1345},
annote = {Keywords: Polygons, polygonization, random polygons, connected configuration space}
}
|
Keywords: |
|
Polygons, polygonization, random polygons, connected configuration space |
|
Collection: |
|
25th International Symposium on Theoretical Aspects of Computer Science |
|
Issue Date: |
|
2008 |
|
Date of publication: |
|
06.02.2008 |
