Jeff Erickson's Publications by Subject

Please read the copyright notice.

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!


Personal favorites

These are the ten 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.
[PDF] Efficiently hex-meshing things with topology
[PDF] Transforming curves on surfaces redux
[PDF] Tracing compressed curves in triangulated surfaces
[PDF] Maximum flows and parametric shortest paths in planar graphs
[PDF] Homology flows, cohomology cuts
[PDF] Optimally cutting a surface into a disk
[PDF] Dense point sets have sparse Delaunay triangulations
[PDF] Raising roofs, crashing cycles, and playing pool:
Applications of a data structure for finding pairwise interactions
[PDF] New lower bounds for Hopcroft's problem
[PDF] Lower bounds for linear satisfiability problems

Ancient history

Over the years I have developed the habit of reading (or at least trying to read) the original works describing classical geometric, topological, and algorithmic results. This is a practice I strongly recommend. Most of these old papers are surprisingly readable, if you can overcome the language barrier. (To quote Doctor Strange: I'm fluent in Google Translate. Sadly, Google Translate is not fluent in 18th century academic Latin.) These old works also offer surprising insights into the mathematical and personal character of their authors. The following papers grew directly out of this historical pursuit; each paper directly builds on, extends, or improves a result that was at least 75 years old at the time the paper was written.
[PDF] How to morph graphs on the torus [Steinitz 192x], [Cairns 1944]
[PDF] A toroidal Maxwell-Cremona-Delaunay correspondence [Maxwell 1864]
[PDF] Optimal curve straightening is ∃R-complete [Gauss 183x]
[PDF] Untangling planar curves [Steinitz 1916]
[PDF] Detecting weakly simple polygons [Meister 1770]
[PDF] Transforming curves on surfaces redux [Dehn 1912]
[PDF] Arbitrarily large neighborly families of congruent symmetric convex 3-polytopes [Tietze 1905]

Combinatorial and computational topology

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

[PDF] Chasing puppies: Mobile beacon routing on closed curves
[PDF] Recognizing weakly simple polygons
[PDF] Untangling planar curves
[PDF] Electrical reduction, homotopy moves, and defect
[PDF] Detecting weakly simple polygons
[PDF] Transforming curves on surfaces redux
[PDF] Shortest non-crossing walks in the plane
[PDF] Walking your dog in the woods in polynomial time
[PDF] Tightening non-simple paths and cycles on surfaces

Embedded graphs

[PDF] Planar and toroidal morphs made easier
[PDF] How to morph graphs on the torus
[PDF] A toroidal Maxwell-Cremona-Delaunay correspondence
[PDF] Topologically trivial closed walks in directed surface graphs
[PDF] Four shortest vertex-disjoint paths in planar graphs
[PDF] Lower bounds for electrical reduction on surfaces
[PDF] Untangling planar curves
[PDF] Detecting weakly simple polygons
[PDF] A near-optimal approximation algorithm for asymmetric TSP on embedded graphs
[PDF] Multiple-source shortest paths in embedded graphs
[PDF] Global minimum cuts in surface-embedded graphs
[PDF] Shortest non-crossing walks in the plane
[PDF] Maximum flows and parametric shortest paths in planar graphs
[PDF] Computing replacement paths in surface-embedded graphs
[PDF] Minimum cuts and shortest non-separating cycles via homology covers
[PDF] Minimum cuts and shortest homologous cycles
[PDF] Homology flows, cohomology cuts

Combinatorial surfaces

[PDF] Multiple-source shortest paths in embedded graphs
[PDF] Combinatorial optimization of cycles and bases
[PDF] Shortest non-trivial cycles in directed surface graphs
[PDF] Minimum cuts and shortest non-separating cycles via homology covers
[PDF] Computing the shortest essential cycle
[PDF] Finding one tight cycle
[PDF] Splitting (complicated) surfaces is hard
[PDF] Greedy optimal homotopy and homology generators
[PDF] Optimally cutting a surface into a disk

Other cell complexes

[PDF] Efficiently hex-meshing things with topology
[PDF] Tracing compressed curves in triangulated surfaces
[PDF] Combinatorial optimization of cycles and bases
[PDF] Vietoris-Rips complexes of planar point sets
[PDF] Testing contractibility in planar Rips complexes
[PDF] Flipping cubical meshes
[PDF] Vertex-unfoldings of simplicial manifolds

Voronoi diagrams and Delaunay triangulations

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!

[PDF] A toroidal Maxwell-Cremona-Delaunay correspondence
[PDF] Empty-ellipse graphs
[PDF] Output-sensitive algorithms for computing nearest-neighbor decision boundaries
[PDF] Uniform samples of generic surfaces have nice Delaunay triangulations
[PDF] Dense point sets have sparse Delaunay triangulations
[PDF] Arbitrarily large neighborly families of congruent symmetric convex 3-polytopes
[PDF] Nice point sets can have nasty Delaunay triangulations
[PDF] New algorithms for minimum measure simplices and one-dimensional weighted Voronoi diagrams

Reconfiguring polygonal chains

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.

[PDF] Flat-state connectivity of linkages under dihedral motions
[PDF] Preprocessing chains for fast dihedral rotations is hard or even impossible
[PDF] Flipturning polygons
[PDF] Reconfiguring convex polygons

Geometric range searching

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.
[PDF] Efficient tradeoff schemes in data structures for moving objects
[PDF] On the complexity of halfspace volume queries
[PDF] Indexing moving points
[PDF] Finite-resolution hidden surface removal
[PDF] Raising roofs, crashing cycles, and playing pool:
Applications of a data structure for finding pairwise interactions
[PDF] Efficient searching with linear constraints
[PDF] Geometric range searching and its relatives
[PDF] Space-time tradeoffs for emptiness queries
[PDF] New lower bounds for halfspace emptiness
[PDF] New lower bounds for Hopcroft's problem

Algorithms for continuously changing data

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 Julien Basch, Leo Guibas, and others.
[PDF] Efficient tradeoff schemes in data structures for moving objects
[PDF] Spacetime meshing with adaptive coarsening and refinement
[PDF] Building spacetime meshes over arbitrary spatial domains
[PDF] Algorithmic issues in modeling motion
[PDF] Indexing moving points
[PDF] Kinetic collision detection for two simple polygons
[PDF] Separation-sensitive collision detection for convex objects
[PDF] Raising roofs, crashing cycles, and playing pool:
Applications of a data structure for finding pairwise interactions
[PDF] Kinetic binary space partitions for intersecting segments and disjoint triangles

Mesh generation

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 models.
[PDF] Efficiently hex-meshing things with topology
[PDF] Spacetime meshing with adaptive refinement and coarsening
[PDF] Flipping cubical meshes
[PDF] Building spacetime meshes over arbitrary spatial domains
[PDF] Dense point sets have sparse Delaunay triangulations
[PDF] Nice point sets can have nasty Delaunay triangulations

Realistic geometric complexity

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.
[PDF] Smoothing the gap between NP and ∃ℝ
[PDF] Empty-ellipse graphs
[PDF] Local polyhedra and geometric graphs
[PDF] Uniform samples of generic surfaces have nice Delaunay triangulations
[PDF] Dense point sets have sparse Delaunay triangulations
[PDF] Arbitrarily large neighborly families of congruent symmetric convex 3-polytopes
[PDF] Nice point sets can have nasty Delaunay triangulations
[PDF] Indexing moving points
[PDF] Finite-resolution hidden surface removal
[PDF] Kinetic collision detection for two simple polygons
[PDF] Separation-sensitive collision detection for convex objects
[PDF] Kinetic binary space partitions for intersecting segments and disjoint triangles

Explicit lower bounds

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.")
[PDF] Fusible numbers and Peano Arithmetic
[PDF] Minimum-cost coverage of point sets by disks
[PDF] Lower bounds for external algebraic decision trees
[PDF] On the complexity of halfspace volume queries
[PDF] Space-time tradeoffs for emptiness queries
[PDF] New lower bounds for halfspace emptiness
[PDF] Lower Bounds for Fundamental Geometric Problems
[PDF] New lower bounds for convex hull problems in odd dimensions
[PDF] New lower bounds for Hopcroft's problem
[PDF] Lower bounds for linear satisfiability problems
[PDF] Better lower bounds on detecting affine and spherical degeneracies

Other hardness results

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.")
[PDF] Optimal curve straightening is ∃R-complete
[PDF] Topologically trivial closed walks in directed surface graphs
[PDF] Minimum cuts and shortest homologous cycles
[PDF] Necklaces, convolutions, and X+Y
[PDF] Splitting (complicated) surfaces is hard
[PDF] Minimum-cost coverage of point sets by disks
[PDF] Lower bounds for external algebraic decision trees
[PDF] Separating point sets in polygonal environments
[PDF] On the least median square problem
[PDF] Optimally cutting a surface into a disk
[PDF] On the complexity of halfspace volume queries
[PDF] Preprocessing chains for dihedral rotations is hard or even impossible
[PDF] Space-time tradeoffs for emptiness queries
[PDF] New lower bounds for halfspace emptiness
[PDF] Lower Bounds for Fundamental Geometric Problems
[PDF] New lower bounds for convex hull problems in odd dimensions
[PDF] On the relative complexities of some geometric problems
[PDF] New lower bounds for Hopcroft's problem
[PDF] Lower bounds for linear satisfiability problems
[PDF] Better lower bounds on detecting affine and spherical degeneracies

Computer Science Education

[PDF] Algorithms (my free textbook)
[PDF] Auto-graded scaffolding exercises for theoretical computer science

Miscellaneous

This is work that doesn't really fit into any of the earlier categories.
[PDF] Fusible numbers and Peano Arithmetic
[PDF] Unfolding and dissection of multiple cubes
[PDF] Capturing a convex object with three discs
[PDF] Finding longest arithmetic progressions
[PDF] Sowing games
[PDF] New Toads and Frogs results
[PDF] 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