DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2008.1345

Connecting Polygonizations via Stretches and Twangs

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

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

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

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)

Copy BibTex To Clipboard

@InProceedings{damian_et_al:LIPIcs.STACS.2008.1345,
  author =	{Damian, Mirela and Flatland, Robin and O'Rourke, Joseph and Ramaswani, Suneeta},
  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 =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.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}
}

Search Results

Documents authored by Ramaswani, Suneeta

Connecting Polygonizations via Stretches and Twangs

Abstract

Cite as

Thanks for your feedback!

Could not send message