Connecting Polygonizations via Stretches and Twangs

Damian, Mirela; Flatland, Robin; O'Rourke, Joseph; Ramaswani, Suneeta

doi:10.4230/LIPIcs.STACS.2008.1345

Document

Connecting Polygonizations via Stretches and Twangs

Authors Mirela Damian, Robin Flatland, Joseph O'Rourke, Suneeta Ramaswani

Part of: Volume: 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Symposium on Theoretical Aspects of Computer Science (STACS)
License: Creative Commons Attribution-NoDerivs 3.0 Unported license
Publication Date: 2008-02-06

PDF

File

PDF

LIPIcs.STACS.2008.1345.pdf

Filesize: 412 kB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2008.1345
URN: urn:nbn:de:0030-drops-13457

Subject Classification

Keywords

Polygons
polygonization
random polygons
connected configuration space

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get BibTex

Mirela Damian, Robin Flatland, Joseph O'Rourke, and Suneeta Ramaswani. Connecting Polygonizations via Stretches and Twangs. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 217-228, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008) https://doi.org/10.4230/LIPIcs.STACS.2008.1345

Author Details

Mirela Damian

Robin Flatland

Joseph O'Rourke

Suneeta Ramaswani

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail