10.4230/LIPICS.STACS.2008.1345
Damian, Mirela
Mirela
Damian
Flatland, Robin
Robin
Flatland
O'Rourke, Joseph
Joseph
O'Rourke
Ramaswani, Suneeta
Suneeta
Ramaswani
Connecting Polygonizations via Stretches and Twangs
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Article
Polygons
polygonization
random polygons
connected configuration space
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
2008
2008-02-06
2008-02-06
2008-02-06
en
urn:nbn:de:0030-drops-13457
10.4230/LIPIcs.STACS.2008
978-3-939897-06-4
1868-8969
10.4230/LIPIcs.STACS.2008
LIPIcs, Volume 1, STACS 2008
25th International Symposium on Theoretical Aspects of Computer Science
2013
1
20
217
228
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
1
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
422635 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 1, 25th International Symposium on Theoretical Aspects of Computer Science, pages 217-228