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
Last updated June 14, 2022 by