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 category!
How to morph graphs on the torus [Steinitz 192x], [Cairns 1944] A toroidal Maxwell-Cremona-Delaunay correspondence [Maxwell 1864] Optimal curve straightening is ∃R-complete [Gauss 183x] Untangling planar curves [Steinitz 1916] Detecting weakly simple polygons [Meister 1770] Transforming curves on surfaces redux [Dehn 1912] Arbitrarily large neighborly families of congruent symmetric convex 3-polytopes [Tietze 1905]
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.
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 McGill University's Bellairs Research Institute in Barbados.
Flat-state connectivity of linkages under dihedral motions Preprocessing chains for fast dihedral rotations is hard or even impossible Flipturning polygons Reconfiguring convex polygons
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 he does.
— 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
quoted by 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
![[PDF]](pix/pdf.gif){kind=small}
![[PDF]](pix/nopdf.gif){kind=small}