Paper by Erik D. Demaine

Reference:

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.

Abstract:

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.

Comments:

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

Length:

The paper is 10 pages.

Availability:

The paper is available in PDF (2751k).

See information on file formats.

[Google Scholar search]

Related papers:

Balloons_ShapingSpace2 (Balloon Polyhedra)