Please read the
Each title below is a link to the abstract, publication history,
copyright information, and electronic
copies of that paper. The square icons are direct links to the most
recent electronic versions. A more
detailed reverse-chronological list of my
papers is also available. Many papers appear in more than one
These are the papers I'm currently most proud of—some because the problems are cool, some because the proofs are elegant, and some just because they required a lot of hard work. These are not necessarily my most cited papers, or the papers for which I am best known. My taste may be different from yours. For that matter, my taste now may be different from my taste five years ago, or five years from now.
Computational topology is a rapidly maturing research area at the
intersection of mathematics and computer science, focused on the
development of efficient algorithms for topological problems arising
either directly from topology, from theoretical computer science, or
from other areas of computing. Algorithmic techniques have been
ubiquitous in topology since its inception more than a century ago, but the
efficiency of topological algorithms and their applicability to other
computing domains are relatively recent areas of study. Results in
this area combine classical mathematical techniques from
combinatorial, geometric, and algebraic topology with more recent
algorithmic tools from optimization and computational geometry. Plus,
you get to draw lots of donuts! And squiggles!
Most of my work in this area involves one-dimensional objects—curves and graphs—embedded in the plane or on some other surface. I've arbitrarily subdivided these papers into three sub-categories, depending on whether the primary object of study is a curve on some surface (possibly represented by a closed walk in some embedded graph), a graph embedded on some surface (in which one wants to compute graphy things like shortest paths and maximum flows), or a surface represented by a graph embedding. Admittedly, this subdivision is deeply spongy; several papers fall under multiple sub-categories.
Curves on surfaces
Other cell complexes
Voronoi diagrams are everywhere, from turtle shells to giraffe
skins to foam in the kitchen sink. Along with their combinatorial
duals, Delaunay triangulations, they have been an object of formal
scientific study for well over a hundred years. In computer science,
they have applications ranging from nearest neighbor searching, to
color quantization, to reconstruction of surfaces from digital images.
Despite all this attention, there are still questions left to answer!
A polygonal chain is a sequence of line segments joined end-to-end.
These papers study the configuration spaces of polygonal chains under
simple classes of pivot operations, such as rotating a subchain around
an edge, cutting out a subchain and regluing it backwards, or flexing
a constant number of angles. Problems in this area have applications
in robot motion planning and molecular modeling. Almost all of the
work in this category was done at annual workshops run by Godfried Toussaint at
Institute in Barbados.
A typical geometric range searching problem has the following form.
Given a set of points in some low-dimensional space, build a data
structure that allows us to quickly count or retrieve the points in an
arbitrary query region. Typical query regions include boxes,
simplices, spheres, and halfspaces. Range searching is an extremely
common problem in databases, but it also has applications in computer
graphics, robotics, and many other areas.
Everything in the real world moves and changes over time. Modeling or
interacting with the real world requires understanding that motion and
designing algorithms to handle it. For example, any simulation of
moving physical objects must detect collisions between objects (and
update the motion of the colliding objects). Many of these papers
work within the
kinetic data structure framework originally developed by
Leo Guibas, and others.
Meshes are used in many research areas to decompose complex objects or
domains into simple regions. For example, meshes are used for
computing numerical solutions of partial differential equations
arising in physical simulations; graphics, CAD, and geographic
information systems use surface meshes to represent complex geometric
Algorithms are traditionally designed and analyzed for efficiency only
in the worst case, but worst-case inputs for many problems are often
highly contrived. As a result, many simple geometric algorithms,
heuristics, or "hacks" perform often considerably better than the
theory predicts. These papers consider geometric algorithms in more
realistic input models. The goal here is to identify useful
combinatorial and geometric features of real geometric data, and then
either analyze existing algorithms in light of those features, or
develop new algorithms to exploit them.
Most theoretical computer science research focuses on developing efficient algorithms and data structures, in an attempt to find the fastest possible solution for a given problem. The flip side of this endeavor is proving lower bounds, that is, to quantify the inherent difficulty of solving a problem. In a few rare cases, this difficulty can be quantified precisely, at least in certain models of computation. ("Sorting requires Ω(n log n) comparisons. The Fermat-Weber problem cannot be solved exactly.")
Most theoretical computer science research focuses on developing efficient algorithms and data structures, in an attempt to find the fastest possible solution for a given problem. The flip side of this endeavor is proving lower bounds, that is, to quantify the inherent difficulty of solving a problem. This difficulty is most often formalized by comparison to some other presumably hard problem. ("Graph coloring is NP-hard. Two-dimensional motion planning is 3SUM-hard.")
This is work that doesn't really fit into any of the earlier categories.
Thus, be it understood, to demonstrate a theorem, it is neither
necessary nor even advantageous to know what it means.... [A] machine
might be imagined where the assumptions were put in at one end, while
the theorems came out at the other, like the legendary Chicago machine
where the pigs go in alive and come out transformed into hams and
sausages. No more than these machines need the mathematician know what
— Henri Poincaré (1854-1912)
I have come to the conclusion that the making of laws is like the
making of sausages—
the less you know about the process the
more you respect the result.
— unknown Illinois legislator (apocryphally
attributed to Otto von Bismarck), c. 1878
Frank W. Tracey, The Report of the Committee on
Uniform Laws of the American Bankers' Association,
15 Banking L.J. 542, 542 (1898).
People who love sausage and respect the law should never watch either
one being made.
— Mark Twain