Connecting Polygonizations via Stretches and Twangs

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



PDF
Thumbnail PDF

File

LIPIcs.STACS.2008.1345.pdf
  • Filesize: 412 kB
  • 12 pages

Document Identifiers

Author Details

Mirela Damian
Robin Flatland
Joseph O'Rourke
Suneeta Ramaswani

Cite AsGet 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

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.
Keywords
  • Polygons
  • polygonization
  • random polygons
  • connected configuration space

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail