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 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. Your taste may be different from mine. For that matter, my taste may be different from mine five years ago.
[PDF] Tracing compressed curves in triangulated surfaces
[PDF] Homology flows, cohomology cuts
[PDF] Empty-ellipse graphs
[PDF] Optimally cutting a surface into a disk
[PDF] Dense point sets have sparse Delaunay triangulations
[PDF] Arbitrarily large neighborly families of congruent symmetric convex 3-polytopes
[PDF] Indexing moving points
[PDF] Raising roofs, crashing cycles, and playing pool:
Applications of a data structure for finding pairwise interactions
[PDF] New lower bounds for convex hull problems in odd dimensions
[PDF] New lower bounds for Hopcroft's problem

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 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!

Topology in the Plane

[PDF] Multiple-source shortest paths in embedded graphs
[PDF] Shortest non-crossing walks in the plane
[PDF] Maximum flows and parametric shortest paths in planar graphs
[PDF] Walking your dog in the woods in polynomial time
[PDF] Testing contractibility in planar Rips complexes
[PDF] Vietoris-Rips complexes of planar point sets

Graphs on Surfaces

[PDF] A near-optimal approximation algorithm for asymmetric TSP on embedded graphs
[PDF] Transforming curves on surfaces redux
[PDF] Multiple-source shortest paths in embedded graphs
[PDF] Combinatorial optimization of cycles and bases
[PDF] Global minimum cuts in surface-embedded graphs
[PDF] Shortest non-trivial cycles in directed surface 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
[PDF] Computing the shortest essential cycle
[PDF] Finding one tight cycle
[PDF] Splitting (complicated) surfaces is hard
[PDF] Tightening non-simple paths and cycles on surfaces
[PDF] Greedy optimal homotopy and homology generators
[PDF] Optimally cutting a surface into a disk

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] 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] 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 cannoot be solved exactly.")
[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] 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

Miscellaneous

This is work that doesn't really fit into any of the earlier categories.
[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

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 03 Apr 2013