6.849: Geometric Folding Algorithms: Linkages, Origami, Polyhedra (Fall 2012)
[Home]
[Problem Sets]
[Project]
[Lectures]
[Problem Session Notes]
Project
2012 Projects
Here is a selection of the 20 projects, and resulting publications,
from 6.849 in 2012:
- “On Wrapping Spheres and Cubes with Rectangular Paper” by Alex Cole, Erik D. Demaine, and Eli Fox-Epstein, published at JCDCG^2 2013
Proves many upper and lower bounds on when an x × y rectangular piece of paper can wrap a unit sphere and unit cube (an open problem posed in Lecture 4).
- “Uniqueness of Optimal Cube Wrapping” by Qinxuan Pan, published at CCCG 2014
Proves that the optimal wrapping of a cube by the smallest possible square
of paper (from Lecture 4) is in fact unique.
- “PCB Origami: A material-based design approach to computer-aided foldable electronic devices by Yoav Sterman, Erik D. Demaine, and Neri Oxman, published at MR/JMD 2013
Explores the use of material with embedded electronics such as PCB (Printed Circuit Boards) as the medium for origami folding in order to create an interactive folding experience and to generate foldable objects with added functionalities.
- “Joining Unfoldings of 3-D Surfaces” by Cynthia Sung, Erik D. Demaine, Martin L. Demaine, and Daniela Rus, published at MR/JMD 2013
Algorithmic proof that two nonoverlapping unfoldings of two surfaces can be combined to make a nonoverlapping unfolding of the surface resulting from joining along an edge, with applications to printable robots.
- “Rapid Prototyping of Folding Structures” by Sam Calisch
Several experiments in rapid prototyping folding structures via vinyl cutter, laser cutting, sewing, creasing wheel, laser welding, etc.
- “A Practical Implementation of Kempe’s Universality Theorem” by Yanping Chen, Laura Hallock, Eric Söderström, Xinyi Zhang
A JavaScript simulation implementing Kempe’s Universality Theorem to construct linkages constrained to a user-inputted curve.
Requirements
Other than problem sets,
the main requirement for this class is the project.
The project consists of at least two components:
- A paper describing what you did.
This should be a well-written document describing the problem
you tackled (be it an artistic, implementation, mathematical, or writing
challenge), what approaches you took, what difficulties you encountered,
and what results you found, in addition to citing the relevant literature.
Aim for on the order of 10 pages, say in the range 5–20 pages.
- A presentation describing what you did
(or how far you've gotten at the time of presentation).
You should prepare slides as PDF or PowerPoint, and you may also demo
any software you wrote. All files should be sent to the staff by
5am on the day of your presentation so that they can be loaded onto
our laptop. Any complicated setups (in particular software) should be
sent by noon the previous day so that we can test.
If you absolutely must use your laptop, let us know ahead of time.
Pure blackboard presentations are discouraged except for the experienced.
The exact length is to be determined, but the presentations
will be during normal lecture time.
- If your project involves writing software, then you should submit
the source code.
If your project involves a physical object, you
should show it during your presentation.
Projects can take many different forms.
Here are the five main general categories:
- Build or design a physical structure
that uses ideas from this class.
The structure might be furniture, architecture, sculpture, tool,
or illustration.
Your work should be both aesthetically compelling and
technically grounded (though the latter need not be explicitly visible).
The structure can be physical or virtual, though in the latter case
the standards will be higher because of the reduced challenge.
(One way to compensate is to make several virtual structures,
e.g., connected in a theme.)
- Implement an algorithm, an illustration of a result, or
a tool for experimenting with a problem.
Typically, a good format for such an implementation is a web applet
(written in
JavaScript,
AJAX,
Java, or
Jython)
but other environments are fine too.
- Pose an open problem (or collection of related open problems).
You might pose open problems related to another field of research
with which you are familiar, or pose something that comes to you out of
the lectures.
Ideally you should think about solving the problem, or how it relates
to other problems.
- Survey a collection of 2 or 3 or more related papers.
You should avoid overlap with the textbook,
Geometric Folding Algorithms:
Linkages, Origami, Polyhedra.
Often it is appropriate to combine with the next type of project:
- Write or substantially improve the Wikipedia articles for
several geometric folding topics.
Here overlap with the textbook is OK.
Be sure to follow Wikipedia guidelines.
- Try to solve an open problem.
This is the most ambitious kind of project, so the expectations in terms
of results are correspondingly lower. What is important is to describe
a clear problem, take (at least) one good approach to that problem, and
describe to what extent it worked or did not work. You should not feel
pressure in terms of grades to produce results, but you should spend
substantial time thinking and trying to solve the problem.
(In particular, if you succeed, you/we can write a research paper and
try to publish it.)
Collaboration is particularly encouraged for projects of this type,
as is participation in the open-problem session.
No matter what you choose, project proposals must be approved by Erik.
You should do this as soon as possible, and no later than
Monday, October 29, 2012.
Deadlines
Project proposals are due Monday, October 29, 2012,
via email to 6849-staff@csail.
By MIT policy, the paper is due on the last regularly scheduled lecture
of this class, Tuesday, December 11, 2012.
The presentation is due somewhat earlier depending on when it gets scheduled
into a lecture slot; if your presentation is earlier, you are expected to have
made less progress, but you should still give a clear description of the
problem you are tackling and what you plan to do.
Collaboration
Collaboration is strongly encouraged, especially for research
projects—this
is often the key to successful research in theoretical computer science.
You can work in a small group of students in the class if you find common
interests. (Students listening to the class will likely have less time to
devote, but they are welcome to participate in a project too.)
You are also welcome to collaborate with anyone outside the class,
including your research supervisor (if you have one)
and including the course staff.
The only constraint for the class is that your own contribution should be
substantial enough, both in terms of solving problems and writing it up.
To evaluate "substantial enough", you should talk to Erik.
In any case, collaborators should be clearly marked in the project proposal,
paper, and presentation.
Ideas
Below is a list of possible project ideas, extracted from
lecture (L) and class (C) notes
and old (O) lecture notes from Fall 2010.
Design/Build/Art
- C06: Design and build a rigid origami structure
- C08: Design a fold-and-cut alphabet, preferably using a small number of simple folds.
- C08: Fold-and-cut art à la Peter Callesen
- C08: Animate motion for 3D polyhedra flattening
- C09: How does real paper behave when folding a hypar?
- L10: Create a Kempe-inspired linkage
- L10: Design linkages to draw letters of the alphabet
- L12: Design and build a tensegrity sculpture
- C14: Design elegant hinged dissections
- C14: Design/build reconfigurable furniture
Coding
- L03: Implement local foldability tester which generates a M/V pattern
- C04: Implement algorithm to generate an arbitrary black/white pixel pattern using checkerboard results
- C05: Improve/extend the interface or capabilities of Tess. Possibly 3D animation through interfacing with Rigid Origami Simulator
- C06: Port Tomohiro Tachi's software to MacOS/Linux
- C08: Implement/improve on a fold-and-cut design tool, ideally including M/V state, degeneracy tool, and folded state. Possibly porting to Javascript.
- C08: Animate motion for 3D polyhedra flattening
- Higher dimension folding visualizer
- L10: Create a Kempe simulation
- C10: Implement Kempe with splines
- L11: JavaScript rigidity/over-bracing/pebble algorithm visualization tool.
- C11: Improve Henneberg construction/puzzle applet, port to web/JavaScript
- L12: Make a virtual tensegrity simulator
- L12: Create a stress/lifting correspondence visualizer
- L13: Implement pointed pseudotriangulation algorithm
- L13: Implement (infinitesimal) locked linkage tester/designer tool
- C14: Implement hinged dissection animator: slender adornments,
general algorithm, and/or polyform algorithm
- C15: Implement continuous blooming algorithms
- L16: Implement orthogonal polyhedra unfolding
- L18: Combine gluing algorithm + Alexandrov algorithm to automate
case studies similar to square or Latin cross
Open Problems
- L02: Pseudopolynomial upper/lower bounds for strip method of folding anything
- PS1: Pset 1 problem 2 many-layers version
- L02: Characterize possible seam placements
- Student: What is the minimum number of creases needed to be removed to make a crease pattern flat-foldable?
- C03: Characterize single-vertex flat-foldable 3D crease patterns
- L04: Optimal wrapping of other shapes by a square
- L04: Optimal wrapping of a cube with an x × y rectangle of paper
- L04: Do there exist other optimal wrappings of a cube by a square?
- L04: Lower bounds for checkerboard folding
- C04: Optimal 2×2 checkerboard folding
- C06: For sufficiently small, rigid motion, is local foldability enough?
- C06: Computational complexity of determining rigid foldability of crease patterns
- C06: Can a paper shopping bag be unfolded from the flat state by adding extra creases?
- C07: Universal folding of polyhedra other than boxes (e.g., polyoctahedra)
- C07: Is there a simpler proof of flat-foldability NP-hardness?
- C07: 3×n map folding [HARD]
- L08/C08: Prove conjectures about linear and circular corridor density
- L08: Prove a lower bound on number of creases in fold-and-cut related to local feature size
- L08: Higher dimensional fold-and-cut
- L08: Instantaneous flattening of polyhedral complexes
- L08: Connected configuration space of polyhedral piece of paper?
- C08: Fold-and-cut with arcs of constant curvature
- C08: Can we continuously flatten nonconvex polyhedra?
- L09: Do triangulated creases for hypars exist for all numbers of pleats and angles?
- L09: Do circular pleats exist? [HARD]
- L09: What is the maximum volume whose surface is a folding of a teabag
- C09: What creases work for regular k-gon pleats?
- C09: Tight bounds for 1D pleat folding (allowing unfolding)
- C09: Find an explicit example of a 1D M/V pattern which requires Ω(n/lg n) folds
- C09: Computational complexity of finding the shortest fold sequence to produce a given 1D M/V pattern (allowing unfolding)
- L10: Characterize when there are folding motions for paper with holes
- L10: Does adding a finite number of creases suffice to allow a folding motion between two folded states if the target folded state does not touch itself?
- L11: Develop a faster 2D rigidity testing algorithm, or prove a lower bound [HARD]
- L11: Characterize generic 3D rigidity [HARD]
- L13: Prove lower bound relating to feature size on number of steps to unfold polygon
- L13: Improve step bound for energy method to unfold polygon
- L13: Is there a unique minimum-energy configuration of a polygon?
- L13: Are there nonlinear locked trees of less than 8 bars?
- L13: Characterize locked linear trees
- L13: Is there a locked equilateral anything in 3D?
- L14: Are there nonslender adornments that never lock?
- C14: 5D and higher dissections
- C14: Efficient algorithm to check for matching Dehn invariants
- C14: Any algorithm to find a dissection when one exists
- L15: Edge unfolding convex prismatoids
- L15: General unfolding polyhedra [HARD]
- L15: Can the star unfolding (or other edge/general unfoldings) be continuously bloomed?
- L15: Edge unfolding a convex polyhedron into o(F) parts?
- C15: Does inverted sun unfolding (source/star) avoid overlap?
- C15: Does every Johnson solid have an edge zipper unfolding?
- C15: Does every convex polyhedron have a general zipper unfolding?
- C15: Which triangulated polyhedra are ununfoldable after attaching
a witch's hat to each face?
- C15: Are 12-face polyhedra unununfoldable?
- C15: Can prismatoids or even prismoids be fully band unfolded?
- C15: Continuous blooming of star unfolding, sun unfolding,
all edge unfoldings, all unfoldings, or orthogonal polyhedra
- L16: Vertex unfolding convex polyhedra [HARD]
- L16: Grid unfolding orthogonal polyhedra [HARD]
- C16: Convex-faced vertex-ununfoldable polyhedron
- C16: Unfolding hexagonal polyhedra
- L17: Prove dependence of algorithms for Alexandrov's Theorem on feature size
- C17: Algorithm for Burago-Zalgaller Theorem guaranteeing nonconvex polyhedron for any gluing
- L18: Complexity of whether a polygon of paper can be glued into a convex polyhedron
- L19: Which polyhedra have common unfoldings?
- L19: Are there two polycubes with no common grid unfolding?
- L19: Close the genus gap for nonorthogonal polyhedra with orthogonal faces
- L19: Minimum perimeter (and area) folding of a sphere
- L20: Complexity of 3D min/max span
- L20: Flat-state connectivity of open chain, orthogonal tree, etc.
- L20: Locked equilateral equiangular fixed-angle chain?
- L21: PTAS or APX-hardness for optimal folding in HP model?
- L21: Unique foldings in nonsquare HP model?
- L21: Minimum number of cuts to unlock an n-bar open chain?
- L21: Smallest k-chain that interlocks with a 2-chain?
- O21: Complexity of shortest flip sequence
- O21: Maximum number of flipturns
- O21: Characterize infinitely deflatable polygons