6.849: Geometric Folding Algorithms: Linkages, Origami, Polyhedra (Fall 2020)

Prof. Erik Demaine; Martin Demaine; TAs Yevhenii Diomidov & Klara Mundilova

Project

The project is the most important requirement of the course. It can take several forms:

• Design/create artwork, furniture, architecture, sculpture, tool, illustration, or other object based on the ideas in the class. Your work should be both aesthetically compelling and technically grounded (though the latter need not be explicitly visible). You may use any medium you wish, including virtual; the challenge of working with your format will be taken into consideration.
• Theoretical contribution to the field: tackle/solve a problem, formulate interesting open problems or conjectures, etc. 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. On the other hand, from past experience, we expect many such results to be produced during class time, and you are encouraged to turn those results into your project(s).
• Survey a few papers on a related topic (not already well-covered by the class or textbook).
• Design a possible new lecture for a future edition of this class.
• Write/record an accessible tutorial for teaching folding to a broad audience.
• Substantially improve the Wikipedia articles for several topics related to the class. Recommended only if you have existing experience editing Wikipedia and with its guidelines. In this case, your project write-up and presentation should summarize the changes you made, why you made the decisions you did, and any challenges you ran into, in addition to linking to new articles and change diffs.
• Implement/visualize one or more algorithms or results, or make a tool to help explore an open problem, from this class or on related topics. We encourage such implementations to be designed as web pages, with code written in CoffeeScript (see our guide for Python programmers) or JavaScript.

You are encouraged to relate the final project to your research interests, and you will not be limited to the topics discussed in class.

Deadlines and Format

• Project proposals are due Thursday, October 15, 2020 at 7pm Eastern, in place of a regular problem set, and should be submitted via Coauthor. See the forthcoming Problem Set for details.
• The course staff will then give feedback on your proposal, including any tips and direction we can think of, and decide whether to approve your project's theme.
• If you decide to change your project direction substantially, it is required that you check in with the course staff to get feedback/approval on the new direction. You should not change the topic of the project, but you may change the form of the project (such as writing a survey if you fail to bring a theoretical contribution).
• Subsequent problem sets will mainly consist of project progress reports to encourage regular progress.
• The project presentation is due on Tuesday, December 1, 2020.
  • Because this is earlier than the project paper deadline, you're expected to have made less progress. You should at least give a clear description of the problem you are tackling and what you plan to do.
  • You must submit your slides in PDF format, and you may also demo any software you wrote or objects you built.
  • You must also record your presentation and submit it as a link (Zoom recording or YouTube unlisted video). See details below.
• By MIT policy, the project paper is due on day of the last regularly scheduled lecture of this class, Monday, December 7, 2020. No extensions are possible.
  • 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 obtained, in addition to citing the relevant literature.
  • Aim for on the order of 10 pages, say in the range 5–20 pages.
  • If your project involves writing software, then you should submit the source code as well; see details below.

Collaboration

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”, talk to the course staff.) In any case, collaborators should be clearly marked in the project proposal, paper, and presentation.

If you work on a team, you will be required to post a short private Coauthor message (in the appropriate thread) summarizing your own contributions to the project(s) you were involved in (when submitting the project). This will let us ensure that everyone makes substantial-enough contributions.

Multiple Projects

You are allowed to work on multiple projects, possibly with different teams. Just make sure that the total amount of work you do sums to at least one “person project unit”. We suggest having one as your main, or one or a small number to which you will make major contributions, along with any number of projects to which you will make minor contributions. We also require that you do some of the writing on at least one project paper, and participate in at least one of the project presentations.

In particular, we'd like projects tackling/solving open problems to match papers as much as possible. For example, instead of working on one project about two small papers, write two smaller projects. Conversely, instead of doing a project about your piece of a larger paper, be a part of a large project to write the entire paper. It's also fine to write up other people's results from open problem solving if they're OK with it (in particular, if they're not planning to do so for their class project) — help with writing is an important contribution to any paper!

Presentation

A project with k presenters will have 8 + 2k minutes for their presentation. So:

• 1-person projects can use 10 minutes
• 2-person projects can use 12 minutes
• 3-person projects can use 14 minutes

Presentations are short, so be efficient in what you cover (and be sure to split the time roughly evenly between speakers). Focus on the problem you tackled, why it's interesting, and what results you came up with, and don't get bogged down in details. It's OK to go a little under time, but do not go over time. Practice your talk, both to measure and to optimize time spent.

To submit your presentation, attach a PDF document to the relevant thread on Coauthor, and then edit that post to have your project's title, to at-mention everyone involved in the project (including yourself), and to add a link to your presentation recording. (If you wish, you can also attach a PowerPoint file, or link to Google Slides or other cloud service, but PDF makes it easy to view the slides within Coauthor.)

Your presentation recording can be done in one of two ways:

• Easy option: Zoom recording
  • Create a Zoom meeting for your project group, and select "Record to Cloud". (MIT's Zoom license supports this feature; if you're using a different Zoom license, make sure it also supports this feature.)
  • After you end the meeting, the meeting creator will get an email about the recording.
  • Open the link, and do the following:
    • Click the "Share" button, and select "Publicly" (under "Share this recording"). This will let students from other organizations see your video.
    • Click "Copy shareable link" and paste that link into Coauthor.
• Advanced option: YouTube unlisted video
  • Record the video how you want (e.g., using OBS Studio),
  • Optionally edit the video how you want (e.g., using Adobe Premiere).
  • Upload the video to your YouTube channel as an Unlisted video.
  • Include the direct link to that video on Coauthor.
• Do not attach a video file to Coauthor.

Project Submission

To submit your final project, attach a PDF document to the relevant thread on Coauthor, and then edit that post to at-mention everyone involved in the project (including yourself), and to add a link to the source files (LaTeX, figures, code, etc.). We require putting all source files into a repository on our MIT Github organization, or an Overleaf document with link sharing turned on, and including a link in your post. If you're unfamiliar with Github, here are some basic instructions:

• Create a new repository with title similar to your project (if you don't have one already), marked Private.
• If you're already using or know how to use Git, push your repository to the resulting remote.
• To just upload your files, go to https://github.com/6849-2020/YOUR-REPO-NAME/upload/master and drag your files in.

Ideas

Design/Build/Art

• C06: Design and build a rigid origami structure
• 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?
• L12: Design and build a tensegrity sculpture
• C14: Design elegant hinged dissections
• C14: Design/build reconfigurable furniture

• L03: Implement local foldability tester which generates a M/V pattern
• 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 platforms other than Windows
• C08: Implement/improve on a fold-and-cut design tool, ideally including M/V state, degeneracy tool, and folded state.
• C08: Animate motion for 3D polyhedra flattening
• Higher dimension folding visualizer
• 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

• 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: Lower bounds for checkerboard folding
• C06: For sufficiently small, rigid motion, is local foldability enough?
• 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: 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: Connected configuration space of polyhedral piece of paper?
• 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 (doubly covered square)?
• 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 to folded states when the paper has holes [HARD]
• 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 chain/tree in 3D?
• L14: Are there nonslender adornments that never lock?
• C14: Dissection in 5D and higher dimensions
• C14: Efficient algorithm to check for matching Dehn invariants
• C14: Any algorithm to find a 3D dissection when one exists
• L15: Edge unfolding convex prismatoids
• L15: General unfolding polyhedra [HARD]
• 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: 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 pairs of 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: 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