Associate Professor
Massachusetts Institute of Technology
|
 |
Professor Erik D. Demaine has been awarded the International
Francqui Chair. He will be hosted by the
Algorithms Group
(Computer Science Department,
Faculty of Sciences,
ULB) and will give a series of
lectures at ULB,
UCL,
VUB, and
FSAGx
| | |
|
Inaugurating
Lecture
Mathematics meets Art, Puzzles, and Magic:
Fun with Algorithms
When: Wednesday November 19, 2008, 4PM
(ULB)
Location: ULB, Salle Dupréel, Institut
de Sociologie (1er étage) – 44 avenue Jeanne, 1050 Bruxelles
Abstract:
Solving and designing puzzles, creating sculpture and architecture,
and inventing magic tricks all lead to fun and interesting algorithmic
problems. I will describe some of our explorations into these areas
(much together with my father, Martin Demaine).
- PUZZLES. Solving a puzzle is like solving a research problem.
Both require the right cleverness to see the problem from the right angle,
and then explore that idea until you find a solution.
The main difference is that the puzzle poser usually guarantees that the
puzzle is solvable. Puzzles also lead to the meta-puzzle of how to
design algorithms that themselves can design families of puzzles.
- ART. Elegant algorithms are beautiful. A special treat is when that
beauty translates visually. Sometimes this is by design, when you
develop an algorithm to compose artwork within a particular family.
Other times the visual beauty of an algorithm just appears,
without anticipation.
- MAGIC. Mathematics is the basis for many magic tricks, particularly
``self-working'' tricks. One of the key people at the intersection of
mathematics and magic is Martin Gardner, whose work has inspired several
of the results described in this talk. Algorithmically, our goal is to
automatically design familes of magic tricks.
|
 |
| |
|
|
| |
|
|
|
|
(Theoretical)
Computer Science is Everywhere
When: Wednesday December 3, 2008, 4PM
Location: Université Catholique de
Louvain, Place Sainte Barbe 1,
Auditoire BARB
92
Abstract:
Theoretical computer science, and the algorithmic way of thinking,
transcends our traditional boundaries. I believe that algorithms are
relevant to every discipline of study, and will give eclectic examples
from the arts and sciences to business and society. The examples span
the spectrum from serious topics like protein folding and decoding
Inka khipu to fun topics like juggling and magic.
|
 |
| |
|
|
| |
|
|
|
|
Origami,
Linkages, and Polyhedra: Geometric Folding Algorithms
When: Thursday February 19, 2009, 4PM
Location: Vrije Universiteit Brussel, Aula Qd room,
Campus
Etterbeek
Abstract:
What forms of origami can be designed automatically by a computer?
What shapes can result by folding a piece of paper flat and making one
complete straight cut? What 3D surfaces can be cut open and unfolded into
a flat piece of paper without overlap? When can a robot arm or protein
be untangled or folded into a desired configuration?
Geometric folding and unfolding is a branch of discrete and computational
geometry that addresses these and many other intriguing questions.
I will give a taste of the many discoveries that have been made in the past
few years, as well as the several exciting problems that remain unsolved.
Folding problems have applications throughout science and engineering,
for example, to safer automobiles, space deployment, manufacturing,
robotics, computer graphics, and protein folding.
|
 |
| |
|
|
| |
|
|
|
|
Linkage
Folding: From Erdös to Proteins
When: Thursday March 5, 2009, 4PM
Location: Faculté Universitaire des
Sciences Agronomiques de Gembloux ,
l’auditoire Espace
Senghor, Passage des Déportés 2, 5030 Gembloux. (directions)
Abstract:
Linkages have a long history ranging back to the 18th century in the
quest for mechanical conversion between circular motion and linear motion,
as needed in a steam engine. In 1877, Kempe wrote an entire book of such
mechanisms for "drawing a straight line". (In mathematical circles, Kempe is
famous for an attempted proof of the Four-Color Theorem, whose main ideas
persist in the current, correct proofs.) Kempe designed many linkages which,
after solidification by modern mathematicians Kapovich, Millson, and Thurston,
establish an impressively strong result: there is a linkage that signs your
name by simply turning a crank.
Over the years mathematicians, and more recently computer scientists, have
revealed a deep mathematical and computational structure in linkages, and
how they can fold from one configuration to another. In 1936, Erd\H{o}s posed
one of the first such problems (now solved): does repeatedly flipping a pocket
of the convex hull convexify a polygon after a finite number of flips?
This problem by itself has an intriguingly long and active history; most
recently, in 2006, we discovered that the main solution to this problem,
from 1939, is in fact wrong.
This talk will describe the surge of results about linkage folding
over the past few years, in particular relating to the two problems
described above. These results also have intriguing applications to
robotics, graphics, nanomanufacture, and protein folding.
|
| |
|
|
| |
|
|
|
Back to the Algo Group
