`6885-students@theory.csail.mit.edu`

,
just in case you didn't receive or misplaced one.

- Mon, 13 Sep 2004 01:16:45 -- Lecture tomorrow: Linkages to sign your name
- Tue, 14 Sep 2004 15:59:08 -- Open problem solving session; class tomorrow
- Tue, 14 Sep 2004 19:20:37 -- Re: Open problem solving session; class tomorrow
- Wed, 15 Sep 2004 15:13:10 -- Projects; problem session again; related talk
- Fri, 17 Sep 2004 13:37:07 -- Re: related talk
- Sun, 19 Sep 2004 19:48:19 -- Class tomorrow; problem sessions on Thursday evenings?
- Mon, 20 Sep 2004 22:17:47 -- Problem session on Thursday
- Thu, 23 Sep 2004 11:00:32 -- Problem session tonight in 2-147
- Thu, 23 Sep 2004 22:13:53 -- Problem session notes
- Thu, 30 Sep 2004 17:17:29 -- Problem session tonight in 2-147
- Sun, 3 Oct 2004 22:34:44 -- Class tomorrow: Origami design
- Wed, 6 Oct 2004 08:33:29 -- Class today: Folding & one straight cut
- Wed, 13 Oct 2004 09:24:37 -- Class today: Unfolding polyhedra
- Thu, 14 Oct 2004 14:42:45 -- Problem session today
- Fri, 15 Oct 2004 10:28:06 -- Some more unfoldable maps
- Sat, 16 Oct 2004 16:09:57 -- Robert Lang's lecture
- Tue, 19 Oct 2004 20:17:35 -- Class canceled tomorrow
- Thu, 21 Oct 2004 13:13:42 -- Problem session today at 6pm in 2-147
- Thu, 21 Oct 2004 20:41:31 -- Update on map folding
- Sat, 23 Oct 2004 21:53:48 -- Project & problem set
- Thu, 28 Oct 2004 12:40:51 -- Problem session today at 6pm in 2-147
- Fri, 29 Oct 2004 21:48:53 -- Forthcoming topics
- Fri, 29 Oct 2004 21:49:02 -- Fall Workshop on Computational Geometry
- Thu, 4 Nov 2004 15:17:58 -- Problem session today
- Mon, 8 Nov 2004 10:01:59 -- Class today: Flat-to-flat
- Wed, 10 Nov 2004 10:08:13 -- Today's class; talk tomorrow; guest lecturers
- Sun, 21 Nov 2004 21:42:49 -- Class tomorrow: Map folding & string matching
- Tue, 23 Nov 2004 09:59:17 -- Class tomorrow?
- Tue, 23 Nov 2004 14:22:28 -- Class canceled tomorrow
- Thu, 25 Nov 2004 14:03:19 -- Problem Set 2 up; projects
- Sun, 28 Nov 2004 23:44:13 -- Class tomorrow; evaluations; PS1; projects
- Wed, 1 Dec 2004 08:53:09 -- Class today; project presentations
- Sun, 5 Dec 2004 22:07:13 -- Project presentations tomorrow
- Tue, 7 Dec 2004 18:59:57 -- Final presentations tomorrow

Dear 6.885 students, Welcome to the 6.885-students mailing list. I'll use this list to make any announcements related to the class, in particular, the topics of upcoming lectures. You can find an archive of mailings to this list on the webpage: http://theory.csail.mit.edu/classes/6.885/fall04/ Tomorrow's lecture will talk about Kempe's Universality Theorem: there is a linkage that traces any polynomial curve. This is a nice construction and it gives you a feel for the power of linkages. I'll also talk about a strengthening of the theorem, that there is a linkage that signs your name (traces a piecewise-polynomial curve). It turns out that there seem to be some open issues here, as well as in the original Kempe result. I'll discuss these issues and several possible project ideas, in particular: - Writing a proof of the claim about piecewise-polynomial curves, with one pen or with multiple pens. (In the latter case you can do signatures with multiple components, e.g., dotting an i.) - Determine the complexity of Kempe's construction, and try to improve it. - Implementing an applet that does the general Kempe construction, or one particularly interesting Kempe construction. - Building an art sculpture based on a particularly nice Kempe construction. - Constructing linkages to write each letter of the alphabet (and ideally find a way to concatenate them in any combination). Scanned lecture notes from the first lecture are on the webpage as well, along with a few extra links to some related pages that I mentioned or hinted at during class. In general, lecture notes will appear online shortly after the lecture takes place. Let me know if you have any trouble navigating the notes, spot bugs, or have suggestions for additional references to accompany the notes. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Dear Students, We seem to quickly be running into interesting open problems and ideas that are worth discussing at more length. If you could email me with the following information, then I can try to find a time that satisfies (most) everyone. If enough of you send me schedules today (a bit late notice, I know), I will try to have a vote in class tomorrow. - What times of which days are bad for you (or, if shorter, what times are good for you). We should have at least a 1.5-hour time slot, though whomever can might stay longer if we are on a roll. - The probability and/or frequency you expect to attend (likely/unlikely/unsure and occasionally/often). Tomorrow's lecture will be on rigidity theory, which is about telling whether a linkage can move at all. There is quite an extensive theory for answering this basic question. In particular, there are fast algorithms and good characterizations for determining many kinds of rigidity in 2D. However, many of the same problems are unsolved in 3D. We'll also find rigidity theory useful later on when we talk about locked linkages (which is about when two configurations cannot reach each other, even though the linkage isn't rigid). I've also put up notes from yesterday's class on the webpage: http://theory.csail.mit.edu/classes/6.885/fall04/ Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

P.S. In general, to reduce email volume, please send responses directly to me, not the entire list. On Tue, 14 Sep 2004, Erik Demaine wrote: > Dear Students, > > We seem to quickly be running into interesting open problems and ideas that > are worth discussing at more length. If you could email me with the > following > information, then I can try to find a time that satisfies (most) everyone. > If enough of you send me schedules today (a bit late notice, I know), > I will try to have a vote in class tomorrow. > > - What times of which days are bad for you > (or, if shorter, what times are good for you). > We should have at least a 1.5-hour time slot, > though whomever can might stay longer if we are on a roll. > > - The probability and/or frequency you expect to attend > (likely/unlikely/unsure and occasionally/often). > [...]

Three things on 6.885: 1. Notes from today's lecture are up, including a new project idea: a Henneberg puzzle game. Please send me email when you find a project that attracts you, and we can discuss it in further detail. 2. My lack of success in finding a good time for the problem-solving session suggests that perhaps we should look at evenings. Please send me email with explicit BAD times that you cannot possibly make, throughout Monday to Friday. (Though I'll avoid Friday evenings.) If I don't hear from you, I will assume that what you've already sent me is a complete list of bad times; but if you sent me good times only, or you didn't send me anything, and are interested in the problem session, send me (another) email. 3. Enclosed below is an abstract of a talk in the AI Colloquium Friday that is relevant to class, specifically motion planning of linkages. It's about randomized algorithms for motion planning / reconfiguration of a linkage (or robot) between two desired configurations. From the abstract, it looks like this talk has some cool theoretical content about when random sampling of the configuration space ("probabilistic roadmap algorithms") do well, and it may also mention some of the practical settings in which such motion planning is useful. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/ ---------- Forwarded message ---------- Date: Wed, 15 Sep 2004 12:11:23 -0400 From: CSAIL Event CalendarTo: seminars@csail.mit.edu Subject: TALK:Friday 9-17-04 Randomized Robot Motion Planning Randomized Robot Motion Planning AI Colloquium Series 2004/2005 Speaker: Prof. David Hsu Host: Prof. Daniela Rus Host Affiliation: CSAIL Date: 9-17-2004 Time: 4:00 PM - 5:00 PM Location: 32-D463 (Star Conf. Room) Abstract: Motion planning is a fundamental and yet computationally hard problem in robotics. Over the past decade, random sampling brought tremendous progress to motion planning of robots with many degrees of freedom, by providing an effective tool to capture the connectivity of complex, high-dimensional geometric spaces. It can plan paths for robots with as many as 36 degrees of freedom with relative ease. Despite the success, it is not well understood why random sampling works well for motion planning. In this talk, I will describe the notion of expansive spaces, in an attempt to characterize robot configuration spaces for which random sampling works well (or not so well). I will also show how to construct simple, effective samplers to deal with narrow passages, the main computational bottle-neck faced by randomized motion planning algorithms. For more information please contact: theresa@csail.mit.edu _______________________________________________ Seminars mailing list Seminars@lists.csail.mit.edu http://lists.csail.mit.edu/mailman/listinfo/seminars

On Wed, 15 Sep 2004, Erik Demaine wrote: > 3. Enclosed below is an abstract of a talk in the AI Colloquium Friday that > is relevant to class, specifically motion planning of linkages. It's > about randomized algorithms for motion planning / reconfiguration of a > linkage (or robot) between two desired configurations. From the > abstract, it looks like this talk has some cool theoretical content about > when random sampling of the configuration space ("probabilistic roadmap > algorithms") do well, and it may also mention some of the practical > settings in which such motion planning is useful. It turns out that this talk was rescheduled (or incorrectly advertised). In fact it will be next Tuesday at 4pm. Erik -------------------------------------------------- Randomized Robot Motion Planning AI Colloquium Series 2004/2005 Speaker: Prof. David Hsu Host: Prof. Daniela Rus Host Affiliation: CSAIL Date: 9-21-2004 Time: 4:00 PM - 5:00 PM Location: 32-D463 (Star Conf. Room) Abstract: Motion planning is a fundamental and yet computationally hard problem in robotics. Over the past decade, random sampling brought tremendous progress to motion planning of robots with many degrees of freedom, by providing an effective tool to capture the connectivity of complex, high-dimensional geometric spaces. It can plan paths for robots with as many as 36 degrees of freedom with relative ease. Despite the success, it is not well understood why random sampling works well for motion planning. In this talk, I will describe the notion of expansive spaces, in an attempt to characterize robot configuration spaces for which random sampling works well (or not so well). I will also show how to construct simple, effective samplers to deal with narrow passages, the main computational bottle-neck faced by randomized motion planning algorithms.

Dear Students, Thanks for sending me your schedules for the problem session. The best time that I see at the moment is Thursday evening. Exactly when is variable, but a typical evening time is starting at 6pm. Another possibility is 5pm. Or 5:30pm. If you have a conflict with any time Thursday evening (where evening is defined to start at 5pm, say), please send me email, and I will choose the time to minimize conflicts. If there are a large number of conflicts, I will continue searching, but otherwise I'm afraid I may not be able to satisfy everyone-- my apologies if that happens. Tomorrow's lecture will consist of a few parts: - We will cover some more rigidity, in particular another type of rigidity called infinitesimal rigidity. This a useful and easy-to-check form of rigidity, and it will also allow us to define exactly what we mean by a "generic" realization. - I will describe extensions of rigidity theory to "tensegrities" (of Buckminster Fuller fame) consisting of rigid bars, stretchable struts, and shrinkable cables. - Then I will talk about "locked chains", when chains can be prevented from reaching all configurations when bars aren't allowed to cross (and when they can't). The switch to noncrossing bars might seem sudden, but in fact many of these problems (particularly in the plane) are closely related to rigidity theory. Tomorrow will be mainly about 2D. - In particular, I plan to prove (the combinatorial part of) the "carpenter's rule theorem": that every 2D chain can be unfolded (i.e., open chains can be straightened and closed chains can be convexified). Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Quick update: Lecture notes from today are now on the class webpage. For those interested in the open problem solving session: Please, if you have a conflict with *any time* on Thursday evening >= 5pm, send me email, even if you've already told me about your conflict. In class, Thursday at 5pm seemed to work OK with almost everyone, but I've just heard about the Simple Person's Applied Math seminar which is 5-6pm. I do not have a sense of how many people attend this seminar, so please tell me if you do (among other conflicts). If there are a significant number of people with this conflict, we will move to 6pm this Thursday. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Dear 6.885 students, Our first (optional) open-problem solving session will be tonight at 6pm in 2-147. (The room may change in the future, depending on how we like this one.) I look forward to seeing several of you there! Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Thanks to everyone who made it to the problem session today. We worked on the infinitesimal carpenter's rule problem in 1D, and made some reasonable progress, but haven't solved the problem. One note to those who attended the session: what we thought was a counterexample no longer seems to be (unless I am missing something). When we add a vertex, we should consider both incident bars and place the vertex sufficiently high to prevent both bars from crossing. The algorithm still may not work, for similar reasons, but we'll need a more complicated example to be sure. Let me know your thoughts! You can find notes from the session on the following private webpage: http://theory.csail.mit.edu/classes/6.885/fall04/ps_notes/ (linked to from the class webpage). You'll need to use the same login and password as the textbook. I don't want these notes to be distributed beyond the class participants so that we have time to work through half-baked ideas ourselves. In any case, the notes will be useful mainly to the attendees of the particular session, or those who want to come up to speed on a session they missed. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Apologies for the delay in sending this email. Our second (optional) open-problem solving session will be tonight at 6pm in 2-147. I look forward to seeing several of you there! We will start with a continuation on the infinitesimal carpenter's rule problem (see the notes on the class webpage) and then start a new problem related to origami. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Dear 6.885 Students, My apologies for not announcing the previous three classes, which in particular covered origami foldability. Tomorrow's class will start the topic of origami design. We'll talk mainly about the most basic questions: what 2D and 3D shapes can be folded from a polygonal piece of paper, and how efficiently can those shapes be folded? The answer to the first question is "everything". We know very little about the second question; all but the most basic questions are unsolved. I'll describe several of these open problems. There will be no problem session this week, because I'm away Thursday. Notes from the previous session are currently in preparation by various attendees. Short summary: we have an idea of how to find infinitesimal motions of self-touching chains in the line, assuming all x coordinates are distinct. In fact (this is new), Tim Abbott and Reid Barton think that the y coordinates of any infinitesimal expansive motion of the "orthogonally thickened" non-self-touching chain will work. Even if that's not true, it should be true in the limit as the thickness approaches zero. More soon. This is off in the future, but on the topic of origami design: one of the most famous origami designers and folders in North America, Robert Lang, will be guest-lecturing in class on Monday, November 15. He'll be talking about his algorithms and computer program TreeMaker for designing origami "bases", the starting point of real origami models. He's the author of Origami Design Secrets, which is recommended reading for this class. To come later on: - More information on visiting Michael LaFosse's origami studio (www.origamido.com) in Haverhill, MA for a single two-hour evening session teaching origami, for those who are interested. - Problem Set 1 Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

Dear 6.885 students, Today's class will be mainly about how to fold a piece of paper flat, make one complete straight cut, and unfold the pieces, to produce any desired pattern of cuts on the piece of paper. There are two approaches to solving this problem. Both have close connections to the forthcoming lecture on TreeMaker. At least one of them can also be used to solve the "polyhedron-flattening" problem: collapse a polyhedral piece of paper (like an airbag) flat just by folding, no cuts. There remain a fair number of open problems related to both folding & cutting and polyhedron flattening. Lecture notes from Monday are up, as are problem-session notes from last Thursday. Thanks to Tim Abbott for writing up the latter. I think it's time to bring the work on infinitesimal carpenter's rule out of the problem session and into "paper-writing mode". I think we are close to a solution, and it's mainly a matter of writing it up formally and proving what we believe to be true. Now the question is, among participants of either of the two problem sessions, who would like to be involved as a co-author of the paper to be written? The model is that anyone who has attended is welcome to join in; those who have already contributed are strongly encouraged to join, independent of whether those contributions have panned out in the end. Please let me know whether you're interested. Next week (not tomorrow) we can start a new problem in the problem session. Let me know if you have ideas/preferences. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.lcs.mit.edu/~edemaine/

Dear students, In today's class, we'll start talking about folding and unfolding polyhedra. After introducing the two problems, I'll focus on unfolding: when can you cut along the surface of a polyhedron and unfold it into one piece without overlap? There are two main variations, depending on whether you can just cut along edges of the polyhedron (edge unfolding) or you can cut anywhere along the surface (general unfolding). Today I'll cover most of what's known for edge unfolding, and touch on general unfolding. Most problems in either case are unsolved. There will be a problem session tomorrow at 6pm in 2-147. Let me know ahead of time if there's a problem you'd like to work on. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

A reminder that there will be a problem session today at 6pm in 2-147. I suggest that we work on either map folding or some aspect of polyhedron unfolding, depending on interest. I'm also open to other suggestions. As usual, pizza will be provided at around 7pm. Hope to see you there! Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

Thanks for the strong attendence in yesterday's problem session. While we didn't make a lot of measurable progress, map folding is the sort of problem that takes a while to get comfortable with, and I think many of you are starting to reach that level of comfort from which you may get inspired. So, in next week's problem session, if anyone has some leads/ideas, we will talk about them; otherwise we will switch to polyhedron unfolding. This is to encourage you to keep thinking about map folding between now and then :-). -*- It would be interesting to implement an efficient exhaustive search over map foldings, to find larger examples than what's been done by 1980's programs and by my inefficient programs. In particular, we could try more extensive searches for hardness gadgets, including allowing question marks for creases. This could easily be a project for the class, or just something interesting to pursue on your own (if you're not registered for the class or have a different project). Let me know if you're interested in playing with this. -*- The main possible approaches for polynomial-time algorithms at the moment seem to be: - Show that it's OK to restrict the folding of submaps in a dynamic program. - Characterize the forbidden configurations. In both cases, we are focusing on 2-by-n maps. I know there are people thinking about both approaches. If you have ideas, feel free to send them to me for moderation, or send them directly to the list. For some food for thought, here are some more examples of unfoldable 2-by-n maps from Jacques Justin's 1986 work. He enumerated examples with n <= 7, removed symmetries, discarded configurations that had unfoldable submaps, and discarded configurations with a double "SS" or "NN" patterns in the NEWS encoding (which he says can always be reduced to smaller examples). Map SEWS +-----+-----+-----+-----+-----+ | | | | | | | V V V V | | | | | | | +--V--+--V--+--M--+--V--+--V--+ | | | | | | | M V V M | | | | | | | +-----+-----+-----+-----+-----+ Map SEWN +-----+-----+-----+-----+-----+ | | | | | | | V V V M | | | | | | | +--V--+--V--+--M--+--V--+--V--+ | | | | | | | M V V V | | | | | | | +-----+-----+-----+-----+-----+ Map SWEWS +-----+-----+-----+-----+-----+-----+ | | | | | | | | V M M M M | | | | | | | | +--V--+--V--+--M--+--V--+--M--+--M--+ | | | | | | | | M M M M V | | | | | | | | +-----+-----+-----+-----+-----+-----+ Map SWEWN +-----+-----+-----+-----+-----+-----+ | | | | | | | | V M M M V | | | | | | | | +--V--+--V--+--M--+--V--+--M--+--M--+ | | | | | | | | M M M M M | | | | | | | | +-----+-----+-----+-----+-----+-----+ Map SENWS +-----+-----+-----+-----+-----+-----+ | | | | | | | | V V V V V | | | | | | | | +--V--+--V--+--M--+--M--+--V--+--V--+ | | | | | | | | M V M V M | | | | | | | | +-----+-----+-----+-----+-----+-----+ Map SWEWES +-----+-----+-----+-----+-----+-----+-----+ | | | | | | | | | V M M M M V | | | | | | | | | +--V--+--V--+--M--+--V--+--M--+--V--+--V--+ | | | | | | | | | M M M M M M | | | | | | | | | +-----+-----+-----+-----+-----+-----+-----+ Map SWEWEN +-----+-----+-----+-----+-----+-----+-----+ | | | | | | | | | V M M M M M | | | | | | | | | +--V--+--V--+--M--+--V--+--M--+--V--+--V--+ | | | | | | | | | M M M M M V | | | | | | | | | +-----+-----+-----+-----+-----+-----+-----+ Map SWESWN +-----+-----+-----+-----+-----+-----+-----+ | | | | | | | | | V M M V M V | | | | | | | | | +--V--+--V--+--M--+--V--+--V--+--M--+--M--+ | | | | | | | | | M M M M M M | | | | | | | | | +-----+-----+-----+-----+-----+-----+-----+ Map SWENWS +-----+-----+-----+-----+-----+-----+-----+ | | | | | | | | | V M M M M M | | | | | | | | | +--V--+--V--+--M--+--V--+--V--+--M--+--M--+ | | | | | | | | | M M M V M V | | | | | | | | | +-----+-----+-----+-----+-----+-----+-----+ Map SSESWN +-----+-----+-----+-----+-----+-----+-----+ | | | | | | | | | V V V M V M | | | | | | | | | +--V--+--V--+--V--+--M--+--M--+--V--+--V--+ | | | | | | | | | M M V V V V | | | | | | | | | +-----+-----+-----+-----+-----+-----+-----+ Map SEWEWS +-----+-----+-----+-----+-----+-----+-----+ | | | | | | | | | V V V V V V | | | | | | | | | +--V--+--V--+--M--+--V--+--M--+--V--+--V--+ | | | | | | | | | M V V V V M | | | | | | | | | +-----+-----+-----+-----+-----+-----+-----+ Map SEWEWN +-----+-----+-----+-----+-----+-----+-----+ | | | | | | | | | V V V V V M | | | | | | | | | +--V--+--V--+--M--+--V--+--M--+--V--+--V--+ | | | | | | | | | M V V V V V | | | | | | | | | +-----+-----+-----+-----+-----+-----+-----+ Map SENWNS +-----+-----+-----+-----+-----+-----+-----+ | | | | | | | | | V V V V M V | | | | | | | | | +--V--+--V--+--M--+--M--+--V--+--V--+--V--+ | | | | | | | | | M V M V V M | | | | | | | | | +-----+-----+-----+-----+-----+-----+-----+ Map SENSWN +-----+-----+-----+-----+-----+-----+-----+ | | | | | | | | | V V V M V M | | | | | | | | | +--V--+--V--+--M--+--M--+--M--+--V--+--V--+ | | | | | | | | | M V M V V V | | | | | | | | | +-----+-----+-----+-----+-----+-----+-----+ Map SENNWS +-----+-----+-----+-----+-----+-----+-----+ | | | | | | | | | V V V V V V | | | | | | | | | +--V--+--V--+--M--+--M--+--M--+--V--+--V--+ | | | | | | | | | M V M M V M | | | | | | | | | +-----+-----+-----+-----+-----+-----+-----+ -*- Minor question: I'm wondering whether we should have the food at the beginning of the session instead of the middle, because it seems to lighten up the atmosphere and get people talking. Or maybe it was just coincidence. Let me know if you have a preference. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

FYI, famous origamist Robert Lang will be guest-lecturing in 6.885 on Monday November 15 (what is listed as "the second lecture" below). Also included below are other events as part of an artist in residence. You may also be interested in the other, more general lecture, as well as at least the first workshop. Cheers, Erik -------------------------------------------------------------------- ROBERT LANG ARTIST IN RESIDENCE November 11-17, 2004 ************* Robert J. Lang has been an avid student of origami for over thirty years and is now recognized as one of the world's leading masters of the art, with over 400 designs catalogued and diagrammed. He is noted for designs of great detail and realism, and includes in his repertoire some of the most complex origami designs ever created. His work combines aspects of the Western school of mathematical origami design with the Eastern emphasis upon line and form to yield models that are at once distinctive, elegant, and challenging to fold. They have been shown in exhibitions in Paris, New York, Boston, San Diego, and Tokyo, among others. Dr. Lang was the first Westerner invited to address the Nippon (Japan) Origami Association's annual meeting (in 1992) and has been an invited guest at international origami conventions around the world. Dr. Lang is one of the pioneers of the cross-disciplinary marriage of origami with mathematics; he has been one of the few Western columnists for Origami Tanteidan Magazine, the journal of the Japan Origami Academic Society, and has presented several refereed technical papers on origami-math at mathematical and computer science professional meetings. He has consulted on applications of origami to engineering problems ranging from air-bag design to expandable space telescopes. He is the author or co-author of eight books and numerous articles on origami. Dr. Lang was born in Ohio and raised in Atlanta, Georgia. After a successful career as a physicist and engineer, during which he authored or co-authored over 80 technical publications and 40 patents on semiconductor lasers, optics, and integrated optoelectronics, he is now a full-time origami artist. Dr. Lang resides in Alamo, California. For more information about Dr. Lang's work, visit his website: http://www.langorigami.com/ During his artist in residence at MIT, Dr. Lang will give two lectures, will teach two hands-on origami workshops, and will have a book signing: * The first lecture is for a general audience, and will be about Dr. Lang's origami work, both artistic and mathematical, on Thursday, November 11 at 7pm, in 32-123. Everyone is strongly encouraged to attend. * The first workshop will teach folding techniques, and is for anyone with at least a small amount of experience with origami (but no extensive knowledge or ability is required). This workshop will be on Saturday, November 13 at 2-4pm in 5-134. If you plan to attend, please sign up by emailing edemaine@mit.edu, so that we have a rough head count. * The second lecture is more technical and will go into depth of Dr. Lang's mathematics and algorithms for origami design. It will take place on Monday, November 15 at 11am-12:30pm, in 4-231. Familiarity with mathematics and algorithms will be assumed. * The second workshop is an advanced origami design workshop for a small number of experienced folders who are either looking to start designing their own models or are looking to refine their design skill. The workshop will take place on Tuesday, November 16 at 7-9pm. Anyone interested in this workshop should email edemaine@mit.edu as soon as possible to guarantee space. * Dr. Lang will be signing his latest book, _Origami Design Secrets: Mathematical Models for an Ancient Art_ (A K Peters, 2003), on Tuesday, November 16 at 4pm, at Quantum Books.

Dear Students, I'm afraid that I've been hit with one of the cold viruses going around Cambridge these days. As a consequence, I'm not feeling well enough to finish preparing lecture, so there will be no class tomorrow. Assuming I'm feeling somewhat better, there will still be a problem session on Thursday. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

Dear Students, I'm feeling better enough to run a problem session, so there will be one at 6pm today in 2-147. Dan Scanlon has a proposed solution to the map-folding problem, so he will present his solution and we can all try to verify or destroy it as appropriate :-). Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

The short story is that we didn't solve map folding :-). We spent most of the session trying to prove NP-hardness in the version with "don't care" (wildcard) creases. We did not reach a definitive conclusion, but we could build (in a certain sense) "exactly 1" and "1 or 3" (XOR) gates. We did not see how to get universality out of this. Michael Burr will be writing up notes from the past two sessions (though they will be short--there were several dead ends that will not be written). Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

Dear Students, For those taking the class for credit (and anyone else interested), information about the project and the first problem set are now up on the class webpage: http://theory.csail.mit.edu/classes/6.885/fall04/ My apologies for the delay on this. Please note the following deadlines: Monday, November 1, 2004 (one week) Project proposal deadline [Your proposal need not be final at this point, but I want to make sure people are thinking about projects.] Monday, November 8, 2004 (two weeks) Problem Set 1 due Somewhere in between: Problem Set 2 (the second and final problem set) Project presentation (in class) Wednesday, December 8, 2004 (6.5 weeks) Project paper due Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

Dear Students, There will be a problem session at 6pm today in 2-147. Dan Scanlon has an update on map folding; then we will turn to another problem, unless there are further ideas. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

Dear Students, Just to give you an idea of where the lectures are going: We are approaching (in a couple of weeks) a completion of a "first pass" through all the folding topics--linkage folding, paper folding, polyhedron unfolding, polyhedron folding, and protein folding. Next week will wrap up polyhedron folding and start protein folding; the week after we'll wrap up protein folding. Then, on the following week, we'll have two guest lectures: November 15 -- Robert Lang: The Tree Method of Origami Design November 17 -- Thomas Hull: Rigid Origami At this point, we will have covered many, but not all, subtopics within each main topic. I wanted to get to this point as quickly as possible, to make sure I got to every topic. Next I'll be going to revisit each main topic (probably in roughly the same order) and cover subtopics that I skipped or only skimmed. Here are some of those topics: Linkages - Roadmap algorithm for solving any finite linkage problem in exponential time. - Linkage reconfiguration allowing self-intersection, e.g., turning a polygon inside out; and in confined regions. - Pseudotriangulation algorithm for unfolding 2D chain linkages. - Interlocked 3D chain linkages (including proofs this time). Origami - Application of string matching to all-layers map folding. - Geometric construction via origami, e.g., angle trisection. Polyhedra - More about shortest paths, geodesics, nonoverlap of star unfolding (?). - Nonorthogonal polyhedra with orthogonal faces. If there's anything else you'd like to hear about, or if there are topics from this list that you'd particularly like or not like to hear about, please let me know. I'm flexible! In the last 3 or 4 lectures or so (depending on how many projects we have), we'll have project presentations. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

Dear Students, I think I promised an email about the Fall Workshop on Computational Geometry to be held in the Stata Center on November 19 & 20, 2004. The exact schedule and abstracts are not yet fixed, but you can find a list of accepted talk titles on the following webpage: http://cgw2004.csail.mit.edu/ If you are planning to attend some or all of the workshop, please register ahead of time (for free) so that we can keep an accurate headcount (for food etc.). Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

Sorry for the short notice: There will be a problem session today at 6pm in the usual place, 2-147. Please bring your ideas on map folding and/or unfolding, and then we may move onto some of the protein-folding problems from yesterday. (Lecture notes to be posted momentarily.) This will likely be the last problem session of the semester, because next week I'm hosting Robert Lang, and the following week I'm hosting the Fall Workshop on Computational Geometry (which now has a program up at http://cgw2004.csail.mit.edu/), and the following week is Thanksgiving, and then we are pushing the end of the semester. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

Dear Students, Today's class will continue the protein folding / fixed-angle chain theme and talk about flat-state connectivity--when all the flat states of a fixed-angle linkage are connected to each other via dihedral motions. There are lots of results on when this is the case for various types of linkages, but many other problems remain open. Unfortunately, my voice is weak today, so we'll see how long I hold up. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

Dear Students, Today's class will continue the protein-folding theme. We'll mainly talk about *producible* fixed-angle chains, which have a lot of strong properties and correspond to the geometric constraints on proteins created by the ribosome. We'll then briefly talk about energy models of protein folding. I'm still sick today so class will probably be a little short. Tomorrow, Thursday, at 7pm Robert Lang will be giving a general-audience talk in 32-123. You are encouraged to attend (it's the same time as a problem session would be, so view it as a replacement for that). Then Rob will be giving a guest-lecture in class next Monday, about the tree method for origami design, in mathematical detail. We also have a guest-lecture next Wednesday by Tom Hull, who will talk about rigid origami folding. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

Dear Students, Tomorrow's class will be about a different model of map folding, perhaps the most standard one used to fold real maps. In an "all-layers simple fold", you pick a line to fold along, and fold all layers of paper on one side of the line by 180 degrees. This is a somewhat different model of simple folds than what we looked at before in class (where we saw crimps, end folds, mingling, etc.), and its solution is quite different. Nonetheless you can test for all-layers simple foldability in roughly linear time, using some nice techniques from string matching. See you then, Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

Dear Students, I've heard that a few people will be away tomorrow (because of Thanksgiving). Could you send me a quick email if you plan to attend class tomorrow? If not enough people say yes, I will cancel class. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

Thanks for all your responses. I estimate that about half of you can come tomorrow. So, I'm canceling tomorrow's class. (There is also no problem session on Thursday.) I will work on finishing up Problem Set 2 (alluded to in last week's guest lecturers) and let you know once it's up. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

Dear Students, Problem Set 2 is now online at http://theory.csail.mit.edu/classes/6.885/fall04/psets.html Given the tight timing between this problem set (due in a week) and the project (due in the following week), I'm making Problem Set 2 optional. If you do not complete this problem set, your project will be weighted more heavily. We are also rapidly approaching project presentation time. Could you please check whether your project is correctly listed on http://theory.csail.mit.edu/classes/6.885/fall04/project.html ? I think I am missing one project. If there are indeed 8 projects, we can fit them into the last two lectures-- December 6 & 8. Please let me know your preference for day of presentation. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

Dear Students, Tomorrow's class will be about geometric constructions via origami. In particular, everyone will get to experience angle trisection by a few easy folds. And we'll see exactly what real numbers can be constructed by a set of axioms essentially capturing all possible alignments via simple folds. Wednesday's class will be my last lecture, as well as HKN class evaluations. I also hope to have Problem Set 1 graded by then. Please sign up for one of the two classes next week if you have a preference. Presentations will be approximately 20 minutes long including questions and switchover, so don't use more than 18 minutes. Also let me know if you'd like to meet to discuss your project. Hope you all had a great Thanksgiving! Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

Dear Students, Class today will be on interlocked 3D linkages: short chains that aren't locked by themselves by together are interlocked. We'll see another use of the topological method for proving lockedness, though not all proofs follow this vein. There are also some cool explosion motions for establishing non-interlockedness. As I mentioned, this will be my last lecture, and it will be a bit short because of HKN class evaluations today. The next two lectures will feature project presentations. They will be a little shorter than I mentioned before-- 5 presentations per class at 16 minutes each. Please keep the presentation part to at most 15 minutes. Feel free to discuss with me what you should cover. Remember that it's more important to clearly convey the problem you are working on and the approach you're taking, rather than having particular results. Here is a tentative schedule: MONDAY Michael Burr Finiteness of pops or generic rigidity in 3D Blaise Gassend Limit definitions of semifree folding, and topological proof of infinitesimal carpenter's rule theorem Benjamin Hebert Faster algorithms for testing generic rigidity Hank Hoffmann 3D linkage unfolding using energy Paul Stellman and Satoshi Takahashi Energy unfolding of Single-vertex origami with applications to nano-origami WEDNESDAY Timothy Abbott and Ried Barton Extensions and improvements to Kempe's Universality Theorem Ariel Rideout and Ryan Williams Implementation of straight-skeleton fold-and-cut algorithm Toby Schachman Box pleating Steven Sivek (but can do Monday) 2-by-n map folding Michael Baym There are many great topics--I'm looking forward to it! If for some reason you cannot make Monday, or would strongly prefer Wednesday and haven't yet told me, let me know; there is a chance you can move, if others are kind. Cheers, Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

Dear Students, Tomorrow's schedule is as advertised before: Michael Burr Finiteness of pops or generic rigidity in 3D Blaise Gassend Limit definitions of semifree folding, and topological proof of infinitesimal carpenter's rule theorem Benjamin Hebert Faster algorithms for testing generic rigidity Hank Hoffmann 3D linkage unfolding using energy Paul Stellman and Satoshi Takahashi Energy unfolding of Single-vertex origami with applications to nano-origami I will assume that you are using your own laptop unless you write to me otherwise. Please send me slides by 10am if you are going to use my laptop. You should send me your slides even if you use your own laptop, but it is less time sensitive in that case. Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/

Dear Students, Five more great topics for tomorrow's final class: WEDNESDAY Timothy Abbott and Ried Barton Extensions and improvements to Kempe's Universality Theorem Ariel Rideout and Ryan Williams Implementation of straight-skeleton fold-and-cut algorithm Toby Schachman Box pleating Steven Sivek 2-by-n map folding Michael Baym Interlocked 3D chains See you all there. Cheers, Erik -- Erik Demaine | edemaine@mit.edu | http://theory.csail.mit.edu/~edemaine/