Luftballon-Polyeder: Die Mathematik hinter dem Verdrehen

Computational Balloon Twisting: The Theory of Balloon Polyhedra [pdf]

Dieses Papier begründet das neue Feld der computergestützten Ballonverdrehung, indem es Ballonfiguren und -polyeder als Graphen modelliert. Es werden Algorithmen vorgestellt, um die minimale Anzahl an Ballons für ein gewünschtes Gebilde zu finden oder die kürzeste Gesamtlänge bei gegebener Ballonanzahl. Zudem wird gezeigt, dass die Entscheidung, ob eine optimale Konstruktion mit gleich langen Ballons möglich ist, NP-vollständig ist. Die Autoren, darunter Erik Demaine, verbinden damit Graphentheorie, Eulertouren und das Chinesische-Postboten-Problem mit einer spielerischen Kunstform.