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.

BibTeX

@InProceedings{Balloons_CCCG2008,
  AUTHOR        = {Erik D. Demaine and Martin L. Demaine and Vi Hart},
  TITLE         = {Computational Balloon Twisting:
                   The Theory of Balloon Polyhedra},
  BOOKTITLE     = {Proceedings of the 20th Canadian Conference on
                   Computational Geometry (CCCG 2008)},
  bookurl       = {http://www.cs.mcgill.ca/~cccg2008},
  ADDRESS       = {Montr\'eal, Qu\'ebec, Canada},
  MONTH         = {August 13--15},
  YEAR          = 2008,

  award         = {Invited to special issue of \emph{Computational Geometry: Theory and Applications}.},
  dblp          = {https://dblp.org/rec/conf/cccg/DemaineDH08},
  comments      = {A <A HREF="short.pdf">short version of the paper</A>
                   appeared on pages 139--142.},
  length        = {10 pages},
  unrefereed    = 1,
  papers        = {Balloons_ShapingSpace2},
  category      = {art},
}

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)