Reconfiguring convex polygons

Oswin Aichholzer*, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, Mark Overmars, Michael Soss, Godfried T. Toussaint

*Korrespondierende/r Autor/-in für diese Arbeit

Publikation: Beitrag in einer FachzeitschriftArtikelBegutachtung

Abstract

We prove that there is a motion from any convex polygon to any convex polygon with the same counterclockwise sequence of edge lengths, that preserves the lengths of the edges, and keeps the polygon convex at all times. Furthermore, the motion is "direct" (avoiding any intermediate canonical configuration like a subdivided triangle) in the sense that each angle changes monotonically throughout the motion. In contrast, we show that it is impossible to achieve such a result with each vertex-to-vertex distance changing monotonically. We also demonstrate that there is a motion between any two such polygons using three-dimensional moves known as pivots, although the complexity of the motion cannot be bounded as a function of the number of vertices in the polygon.

Originalspracheenglisch
Seiten (von - bis)85-95
Seitenumfang11
FachzeitschriftComputational Geometry: Theory and Applications
Jahrgang20
Ausgabenummer1-2
DOIs
PublikationsstatusVeröffentlicht - Okt. 2001

Schlagwörter

  • Discrete and Computational Geometry

ASJC Scopus subject areas

  • Angewandte Informatik
  • Geometrie und Topologie
  • Steuerung und Optimierung
  • Theoretische Informatik und Mathematik
  • Computational Mathematics

Fingerprint

Untersuchen Sie die Forschungsthemen von „Reconfiguring convex polygons“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren