Bumpy Pyramid Folding Problem

• Zachary R.Abel

  Department of Mathematics, MIT

• Erik D.Demaine

  Computer Science and Artificial Intelligence Laboratory, MIT

• Martin L.Demaine

  Computer Science and Artificial Intelligence Laboratory, MIT

• Hiro Ito

  School of Informatics and Engineering, The University of Electro-Communications

• Jack Snoeyink

  Department of Computer Science, The University of North Carolina

• Ryuhei Uehara

  School of Information Science, Japan Advanced Institute of Science and Technology

Abstract

Folding problems are investigated for a class of petal (or star-like) polygons P, with an n-polygonal base B surrounded by a sequence of triangles for which adjacent pairs of sides have equal length. Linear time algorithms using constant precision are given to determine if P can fold to a pyramid with flat base B, and to determine a triangulation of B (crease pattern) that allows folding into a bumpy pyramid that is convex. By Alexandrov's theorem, the crease pattern is unique if it exists, but the general algorithm known for this theorem is pseudo-polynomial, with very large running time; ours is the first efficient algorithm for Alexandrov's theorem for a special class of polyhedra. We also show a polynomial time algorithm that finds the crease pattern to produce the maximum volume bumpy pyramid.

Journal

• IPSJ SIG Notes

  IPSJ SIG Notes 2013 (19), 1-7, 2013-10-30

  Information Processing Society of Japan (IPSJ)

Details

• CRID: 1570291227961003520
• NII Article ID: 110009614899
• NII Book ID: AN1009593X
• ISSN: 09196072
• Text Lang: en
• Data Source:
  • CiNii Articles