Connecting Polygonizations via Stretches and Twangs

Mirela Damian, Robin Flatland, Joseph O'Rourke, Suneeta Ramaswami

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

We show that the space of polygonizations of a fixed planar point set S of n points is connected by O(n2) "moves" between simple polygons. Each move is composed of a sequence of atomic moves called "stretches" and "twangs," which walk between weakly simple "polygonal wraps" of S. These moves show promise to serve as a basis for generating random polygons.

Original languageEnglish (US)
Pages (from-to)674-695
Number of pages22
JournalTheory of Computing Systems
Volume47
Issue number3
DOIs
StatePublished - Jan 1 2010

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Keywords

  • Connected configuration space
  • Polygonization
  • Polygons
  • Random polygons

Fingerprint Dive into the research topics of 'Connecting Polygonizations via Stretches and Twangs'. Together they form a unique fingerprint.

  • Cite this