6.885: Folding and Unfolding in Computational Geometry (Fall 2004)

Prof. Erik Demaine

Mailing List Archive

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