"The Universe is full of
magical things
patiently waiting for
our wits to get sharper"
Eden Phillpots
My area of research is
Combinatorial and Computational Geometry. I enjoy working
on both theoretical and applied problems.
I have used
tools from Combinatorics, Graph Theory, Rigidity Theory, Oriented Matroids,
Linear Programming and Computational Algebraic Geometry,
and worked on problems with applications in
Computer Graphics, Graph Drawing, Robotics, Statistics, Data Visualization and,
more recently,
Computational Structural Biology (Protein flexibility, structure, folding,
alignment
- i.e. the problems that exhibit geometrical structure).
Pebble Games for tree-decompositions, and their applications to the flexibility analysis of bar-and-joint (2d),
body-and-bar and body-and-hinge (3d) structures. This is work with my students Audrey Lee and Louis Theran
from UMass, extending the
beautiful and elegant pebble game algorithm for generic rigidity in dimension 2 of Hendrickson and Jacobs.
Here is a link to an implementation of our generalized algorithm, and here is a more recent web site devoted to pebble games, generalizations and applications.
Polyhedral unfolding. Imagine you have a 3d convex polyhedron made of paper. Cut it along a set of edges (a spanning tree
of the 1-skeleton) and unfold it flat.
It is known that sometimes the flattened surface has overlaps. Proving that there always exists a way of cutting it which leads to
no overlaps is an outstanding problem on which many bright minds have worked :-) (it's still wide open). Here is a
page illustrating a partial result, related to a special family of such polyhedra: prismatoids.
Computational Origami. I am interested in understanding folding processes
for rigid origamis. This is a hard problem about which
very little is known. Moving from linkage folding to paper folding adds incredible
complexity. Here is a link to my recent work (with Walter Whiteley)
where we give a complete solution for single-vertex origami folds (i.e. we solve
the inverse kinematics problem).
Kinetic data structures and Morphing. I am interested in the problem of maintaining the planar structure of a graph embedding during a constant velocity motion of the underlying point set.
Here is a description of my current discovery that pointed pseudo-triangulation mechanisms are kinetic planar graphs: they maintain their planarity (and pointedness) throughout the motion.
Protein Folding. I spent part of my 2002-2003 sabbatical at Stanford University,
learning about this fascinating problem and working with
Leo Guibas,
Michael Levitt,
R. James Milgram and students on some problems aiming at understanding the mathematical
and algorithmic foundations of the Protein Folding problem. I'm working on some
problems on 3d linkages, motivated by protein backbone models.
Singularities of hinge structures. This is the beginning of
my excursions (accompanied by knowledgeable co-authors) into the topology of
configuration spaces for linkages of various sorts. I.e. not just bar-and-joint, but also panel-and-hinge
and body-and-hinge. I would like to understand how singularities
can be predicted and how they influence the robustness of the algorithms we may want to
design for planning paths in these configuration spaces.
Motion Planning,
especially for Robot Arms, using tools from Rigidity
Theory and aiming towards applications to studying
Protein Folding processes.
This
page describes
the Carpenter's Rule Problem and the algorithmic
solution I gave based
on pseudo triangulations. Here's a pointed
pseudo-triangulation mechanism in continuous motion.
Look also at this series of two articles in the
American Mathematical Society
What's New in Mathematics
on-line Column Archive, about
Linkages,
the
Carpenter's Rule Problem
,
and my solution based on
pseudo-triangulations.
Pseudo-Triangulations: combinatorial, rigidity-theoretical
and algorithmic properties.
Here's an animated pointed
pseudo-triangulation mechanism, which simulates its purely
contractive or purely expansive motion. And
here is a page devoted
to this intriguing data structure (under construction).
Rigid embeddings of graphs,
mechanisms for tracing planar curves and
lots of neat questions (combinatorial, algebraic and algorithmic)
from Kinematics and Rigidity Theory.
This
page, under construction, illustrates the mechanisms for coupler curves
used in a recent paper for studying bounds on the number of embeddings of minimally rigid graphs.
Computational Statistics: measures of data depth
(multivariate), robust implementation of efficient algorithms.
With applications to
data visualization and outlier identification.
Check the
Location Depth page at Smith, and at
Tufts.
Robust implementation of geometric algorithms.
A description of our robust implementation for
Topological Sweep.
Visibility graphs: characterization, recognition and
variations (floodlight illumination, rectangle visibility graphs).
I left some of these questions in a dormant state for a while, while looking for
ideas elsewhere. Here
is a recently resurscitated one, illustrated by an
applet for rectangle visibility graphs, done by Sue Whitesides' student
Matt Suderman at McGill.
Oriented matroids: the hyperline sequence formalism,
pseudoline arrangements,
the Folkman-Lawrence
topological representation theorem and applications to problems
in Computational Geometry. I plan to eventually make an on-line page devoted to these
questions. Meanwhile, here is a simple open
problem that came out of my work on visibility (floodlight illumination),
in the context of pseudoline arrangements.
Combinatorial and algorithmic properties of
structures such as: thickness 2 graphs (arising in
conjunction with rectangle visibility graphs),
Hamilton Paths and Hamilton Path decomposition of some special
graphs arising from great-circle
arrangements, etc.
Long time ago (before 1989)
I was interested in
Programming Languages and Compilers (esp. LISP, on which I wrote
a book), Formal Languages,
Recursive Function Theory and Logic, and was
particularly fond of Gödel's Incompleteness Theorem and
undecidability results.
My co-authors.
