Paper by Erik D. Demaine

Erik D. Demaine, Martin L. Demaine, and Vi Hart, “Computational Balloon Twisting: The Theory of Balloon Polyhedra”, in Proceedings of the 20th Canadian Conference on Computational Geometry (CCCG 2008), Montréal, Québec, Canada, August 13–15, 2008.

This paper builds a general mathematical and algorithmic theory for balloon-twisting structures, from balloon animals to balloon polyhedra, by modeling their underlying graphs (edge skeleta). In particular, we give algorithms to find the fewest balloons that can make exactly a desired graph or, using fewer balloons but allowing repeated traversal or shortcuts, the minimum total length needed by a given number of balloons. In contrast, we show NP-completeness of determining whether such an optimal construction is possible with balloons of equal length.

A short version of the paper appeared on pages 139--142.

The paper is 10 pages.

The paper is available in PDF (2751k).
See information on file formats.
[Google Scholar search]

Related papers:
Balloons_ShapingSpace2 (Balloon Polyhedra)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated July 25, 2017 by Erik Demaine.