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!
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
Capturing a convex object with three discs Finding longest arithmetic progressions Sowing games New Toads and Frogs results Iterated nearest neighbors and finding minimal polytopes
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
Publications -
Jeff Erickson
(jeffe@cs.uiuc.edu)
02 Feb 2012
![[PDF]](pix/pdf.gif){kind=small}
![[PDF]](pix/nopdf.gif){kind=small}