Jeff Erickson's Publications

Please read the copyright notice.

Each paper title is a link to the abstract, publication history, copyright information, and electronic copies of that paper. Some pages may be out of date. Please send me email if you want a more recent version any paper than you can find here.

A more concise listing of my papers by subject area is also available.

*Stars indicate co-authors who were students when the first version of the paper was submitted. New papers, changes in publication status, and other additions are marked for a few months (or until I remember to unmark them). The square icons are direct links to the most recent electronic versions. If you'd like a hard copy of something, just send me email.

I write everything in LaTeX; you might find some of my macro packages useful.


[PDF] A near-optimal approximation algorithm for asymmetric TSP on embedded graphs
with Anastasios Sidiropoulos
Submitted to the 30th Annual Symposium on Computational Geometry (2014).
[PDF] Efficiently hex-meshing things with topology
Proceedings of the 29th Annual Symposium on Computational Geometry, 37–46, 2013.
Full version submitted to Discrete & Computational Geometry.
[PDF] Transforming curves on surfaces redux
With Kim Whittlesey
Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, 1646–1655, 2013.
[PDF] Multiple-source shortest paths in embedded graphs
With Sergio Cabello and Erin W. Chambers
SIAM Journal on Computing 42(4):1542–1571, 2013.
[PDF] Tracing compressed curves in triangulated surfaces
With Amir Nayyeri*
Discrete & Computational Geometry 49(4):823–863, 2013.
(Special section of invited papers from the 28th Annual Symposium on Computational Geometry)
[PDF] Global minimum cuts in surface-embedded graphs
With Kyle Fox* and Amir Nayyeri*
Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, 1309–1318, 2012.
[PDF] Combinatorial optimization of cycles and bases
Advances in Applied and Computational Topology (Afra Zomorodian, editor), pp. 195–228.
Proceedings of Symposia in Applied Mathematics 70, American Mathematical Society, 2012.
[PDF] Shortest non-trivial cycles in directed surface graphs
Proceedings of the 27th Annual Symposium on Computational Geometry, 236–243, 2011.
[PDF] Shortest non-crossing walks in the plane
With Amir Nayyeri*
Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 279–308, 2011.
[PDF] Computing replacement paths in surface-embedded graphs
With Amir Nayyeri*
Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 1347–1354, 2011.
[PDF] Minimum cuts and shortest non-separating cycles via homology covers
With Amir Nayyeri*
Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 1166–1176, 2011.
[PDF] Computing the shortest essential cycle
With Pratik Worah*
Discrete & Computational Geometry 44(4):912–930, 2010.
[PDF] Maximum flows and parametric shortest paths in planar graphs
Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, 794-804, 2010.
[PDF] Minimum cuts and shortest homologous cycles
With Erin Wolf Chambers and Amir Nayyeri*
Proceedings of the 25th Annual Symposium on Computational Geometry, 377–385, 2009.
[PDF] Homology flows, cohomology cuts
With Erin Wolf Chambers and Amir Nayyeri*
SIAM Journal on Computing 41(6):1605–1634, 2012.
(Special section of invited papers from the 41st Annual ACM Symposium on Theory of Computing)
[PDF] Testing contractibility in planar Rips complexes
With Erin Wolf Chambers* and Pratik Worah*
Proceedings of the 24th Annual ACM Symposium on Computational Geometry, 251–259, 2008.
[PDF] Walking your dog in the woods in polynomial time
With Erin Wolf Chambers*, Éric Colin de Verdière, Sylvain Lazard, Francis Lazarus, and Shripad Thite
Computational Geometry: Theory and Applications 43(3):295–311, 2010.
(Special issue of invited papers from the 24th Annual Symposium on Computational Geometry)
My final contribution to Elsevier. (Here are some reasons.)
[PDF] Vietoris-Rips complexes of planar point sets
With Erin Wolf Chambers*, Vin de Silva, and Robert Ghrist
Discrete & Computational Geometry 44(1):75–90, 2010.
[PDF] Empty-ellipse graphs
With Xavier Goaoc and Olivier Devillers
Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, 1249–1257, 2008.
[PDF] Finding one tight cycle
With Sergio Cabello, Matt DeVos, and Bojan Mohar
ACM Transactions on Algorithms, 6(4):article 61, 2010.
(Special issue of invited papers from the 19th Annual ACM-SIAM Symposium on Discrete Algorithms)
[PDF] Necklaces, convolutions, and X+Y
With David Bremner, Timothy M. Chan, Erik D. Demaine, Ferran Hurtado, John Iacono, Mihai Pătraşcu, Stefan Langerman, Perouz Taslakian*
Algorithmica, in press, December 2012.
Proceedings of the 12th Annual European Symposium on Algorithms, 160–171, 2006.
[PDF] Splitting (complicated) surfaces is hard
With Erin Wolf Chambers*, Éric Colin de Verdière, Francis Lazarus, and Kim Whittlesey
Computational Geometry: Theory and Applications 41(1–2):94–110, 2008.
(Special issue of invited papers from the 22nd European Workshop on Computational Geometry)
[PDF] Minimum-cost coverage of point sets by disks
With Helmut Alt, Esther M. Arkin, Hervé Brönnimann, Sándor P. Fekete, Christian Knauer, Jonathan Lenchner*, Joseph S. B. Mitchell, and Kim Whittlesey
Proceedings of the 22nd Annual ACM Symposium on Computational Geometry, 449–458, 2006.
[PDF] Tightening non-simple paths and cycles on surfaces
With Éric Colin de Verdière
SIAM Journal on Computing 39(8):3784–3813, 2010.
[PDF] Realizing partitions respecting full and partial order information
With Erik D. Demaine, Danny Krizanc, Henk Meijer, Pat Morin, Mark Overmars, and Sue Whitesides
Journal of Discrete Algorithms 6:51–58, 2008.
(Special issue of invited papers from the 16th Australasian Workshop on Combinatorial Algorithms)
[PS] [PDF] Greedy optimal homotopy and homology generators
With Kim Whittlesey
Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 1038–1046, 2005.
[PS] [PDF] Lower bounds for external algebraic decision trees
Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 755–761, 2005.
[PS] [PDF] Efficient tradeoff schemes in data structures for querying moving objects
With Pankaj K. Agarwal, Lars Arge, and Hai Yu*
Proceedings of the 12th Annual European Symposium on Algorithms, 4–15, 2004.
[PDF] Automatic blocking scheme for structured meshing in 2d multiphase flow simulation
With Damrong Guoy
Proceedings of the 13th Annual International Meshing Roundtable, 121–132, 2004.
[PS] [PDF] Spacetime meshing with adaptive refinement and coarsening
With Reza Abedi*, Shuo-Heng Chung*, Yong Fan*, Michael Garland, Damrong Guoy, Robert Haber, John Sullivan, Shripad Thite*, and Yuan Zhou*.
Proceedings of the 20th Annual ACM Symposium on Computational Geometry, 300–309, 2004.
[PS] [PDF] On the least median square problem
With Sariel Har-Peled and David Mount.
Proceedings of the 20th Annual ACM Symposium on Computational Geometry, 273–279, 2004.
[PS] [PDF] Separating point sets in polygonal environments
With Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Mark Overmars, and Sue Whitesides.
Proceedings of the 20th Annual ACM Symposium on Computational Geometry, 10–16, 2004.
[PS] [PDF] On the complexity of halfspace volume queries
With Erik D. Demaine and Stefan Langerman.
Proceedings of the 15th Canadian Conference on Computational Geometry, 159–160, 2003.
[PS] [PDF] Output-sensitive algorithms for computing nearest-neighbor decision boundaries
With David Bremner, Erik D. Demaine, John Iacono, Stefan Langerman, Pat Morin, and Godfried Toussaint.
Proceedings of the 2003 Workshop on Algorithms and Data Structures, 451–461, 2003.
[PS] [PDF] Local polyhedra and geometric graphs
Computational Geometry: Theory and Applications 31(1–2):101–125, 2005.
(Special issue of invited papers from the 19th Annual ACM Symposium on Computational Geometry)
[PS] [PDF] Uniform samples of generic surfaces have nice Delaunay triangulations
Preprint, December 2002.
[PS] [PDF] Capturing a convex object with three discs
With Jean Ponce, Fred Rothganger*, and Shripad Thite*
Proceedings of the 2003 IEEE International Conference on Robotics and Automation, 2242–2247, 2003.
[PS] [PDF] Flipping cubical meshes
With Marshall Bern and David Eppstein.
Engineering with Computers 18(3):173–187, 2002.
(Special issue of invited papers from the 10th International Meshing Roundtable).
arXiv:cs.CG/0108020
[PS] [PDF] Flat-state connectivity of linkages under dihedral motions
With Greg Aloupis*, Erik D. Demaine, Vida Dujmovic'*, Stefan Langerman, Henk Meijer, Ileana Streinu, Joseph O'Rourke, Mark Overmars, Michael Soss, and Godfried Toussaint.
Proceedings of the 13th Annual International Symposium on Algorithms and Computation, 369–380, 2002.
[PS] [PDF] Building spacetime meshes over arbitrary spatial domains
With Damrong Guoy, John Sullivan, and Alper Üngör*.
Engineering with Computers 20(4):342–353, 2005.
Proceedings of the 11th International Meshing Roundtable, 391–402, 2002.
arXiv:cs.CG/0206002
[PS] [PDF] Optimally cutting a surface into a disk
With Sariel Har-Peled.
Discrete & Computational Geometry 31(1):37–59, 2004.
(Special issue of invited papers from the 18th Annual ACM Symposium on Computational Geometry)
arXiv:cs.CG/0207004
[PS] [PDF] Vertex-unfoldings of simplicial manifolds
With Erik D. Demaine*, David Eppstein, George W. Hart, and Joseph O'Rourke.
Discrete Geometry: In Honor of W. Kuperberg's 60th Birthday (András Bezdek, editor), Marcel Dekker, 2003, pp. 215–228.
arXiv:cs.CG/0110054
[PS] [PDF] Preprocessing chains for fast dihedral rotations is hard or even impossible
With Michael A. Soss* and Mark Overmars.
Computational Geometry: Theory and Applications 26(3):235–246, 2003.
arXiv:cs.CG/0204042
[PS] [PDF] Algorithmic issues in modeling motion
by Pankaj K. Agarwal, Leonidas J. Guibas, and 19 others.
ACM Computing Surveys 34(4):550–572, 2002.
[PS] [PDF] Dense point sets have sparse Delaunay triangulations
Discrete & Computational Geometry 33:83–115, 2005.
[PS] [PDF] Arbitrarily large neighborly families of congruent symmetric convex 3-polytopes
With Scott Kim.
Discrete Geometry: In Honor of W. Kuperberg's 60th Birthday (András Bezdek, editor), Marcel-Dekker, 2003, pp. 267–278.
arXiv:math.CO/0106095
[PS] [PDF] Nice point sets can have nasty Delaunay triangulations
Discrete & Computational Geometry 30(1):109–132, 2003.
(Special issue of invited papers from the 17th Annual ACM Symposium on Computational Geometry).
arXiv:cs.CG/0103017
[PS] [PDF] Flipturning polygons
With Oswin Aichholzer, Carmen Cortés, Vida Dujmovic'*, Erik D. Demaine*, Henk Meijer, Mark Overmars, Belén Palop, Suneeta Ramaswami, and Godfried Toussaint
Discrete & Computational Geometry 28:231–253, 2002.
arXiv:cs.CG/0008010
[PS] [PDF] Reconfiguring convex polygons
With Oswin Aichholzer, Erik D. Demaine*, Ferran Hurtado, Mark Overmars, Michael A. Soss*, and Godfried Toussaint.
Computational Geometry: Theory and Applications 20(1–2):85–95, 2001.
(Special issue of invited papers from the 12th Annual Canadian Conference on Computational Geometry)
[PS] [PDF] Indexing moving points
With Pankaj K. Agarwal and Lars Arge.
Journal of Computer and System Sciences 66:207–243, 2003
(Special issue of invited papers from the 19th ACM Symposium on Principles of Database Systems).
[PS] [PDF] Finding longest arithmetic progressions
Manuscript, July 1999.
[PS] [PDF] Finite-resolution hidden surface removal
Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, 901–909, 2000.
arXiv:cs.CG/9910017
[PS] [PDF] Kinetic collision detection for two simple polygons
With Julien Basch*, Leonidas J. Guibas, John Hershberger, and Li Zhang*.
Computational Geometry: Theory and Applications 27:211–235, 2004.
[PS] [PDF] Separation-sensitive collision detection for convex objects
With Leonidas J. Guibas, Jorge Stolfi, and Li Zhang*.
Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 327–336, 1999.
arXiv:cs.CG/9809035
[PS] [PDF] Raising roofs, crashing cycles, and playing pool:
Applications of a data structure for finding pairwise interactions

With David Eppstein.
Discrete & Computational Geometry 22(4):569–592, 1999.
(Special issue of invited papers from the 14th Annual ACM Symposium on Computational Geometry)
[PS] [PDF] Efficient searching with linear constraints
With Pankaj K. Agarwal, Lars Arge, Paolo G. Franciosa*, and Jeffrey Scott Vitter.
Journal of Computer and System Sciences 61(2):192–216, 2000.
(Special issue of invited papers from the 17th ACM Symposium on Principles of Database Systems)
[PS] [PDF] Kinetic binary space partitions for intersecting segments and disjoint triangles
With Pankaj K. Agarwal and Leonidas J. Guibas.
Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 107–116, 1998.
[PS] [PDF] Geometric range searching and its relatives
With Pankaj K. Agarwal.
Advances in Discrete and Computational Geometry
(Bernard Chazelle, Jacob E. Goodman, and Richard Pollack, editors),
Contemporary Mathematics 223, American Mathematical Society Press, 1999, pp. 1–56.
[PS] [PDF] Space-time tradeoffs for emptiness queries
SIAM Journal on Computing 29(6):1968–1996, 2000.
Recent improvements!
[PS] [PDF] New lower bounds for halfspace emptiness
Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 472–481, 1996.
Merged into the journal version of "Space-time tradeoffs for emptiness queries".
[PS] [PDF] Lower Bounds for Fundamental Geometric Problems
Ph.D. dissertation, University of California at Berkeley, July 1996.
[PS] [PDF] New lower bounds for convex hull problems in odd dimensions
SIAM Journal on Computing 28(4):1198–1214, 1999.
[PS] [PDF] Sowing games
Games of No Chance (Richard J. Nowakowski, editor),
Mathematical Sciences Research Institute Publications 29, Cambridge University Press, 1996, pp. 287–297.
[PS] [PDF] New Toads and Frogs results
Games of No Chance (Richard J. Nowakowski, editor),
Mathematical Sciences Research Institute Publications 29, Cambridge University Press, 1996, pp. 299–310.
[PS] [PDF] On the relative complexities of some geometric problems
Proceedings of the 7th Canadian Conference on Computational Geometry, 85–90, 1995.
[PS] [PDF] New lower bounds for Hopcroft's problem
Discrete & Computational Geometry 16(4):389–418, 1996.
(Special issue of invited papers from the 11th Annual ACM Symposium on Computational Geometry)
Recent improvements!
[PS] [PDF] Lower bounds for linear satisfiability problems
Chicago Journal of Theoretical Computer Science 1999(8), 1999.
[PS] [PDF] Better lower bounds on detecting affine and spherical degeneracies
With Raimund Seidel.
Discrete & Computational Geometry 13(1):41–57, 1995.
Erratum in Discrete & Computational Geometry 18:239–240, 1997.
[PS] [PDF] Iterated nearest neighbors and finding minimal polytopes
With David Eppstein.
Discrete & Computational Geometry 11(3):321–350, 1994.
[PS] [PDF] New algorithms for minimum measure simplices and one-dimensional weighted Voronoi diagrams
With David Eppstein.
U. C. Irvine Technical Report 92-55, June 1992.


Lecture notes, web pages, software, etc.


It is true that systems that people use today would be much better if their builders had read the papers published by academicians in the 1960s and 70s. This is a little unfair to the practitioners, though, because nobody has ever shown that academic computer science journal articles have any effect on either practical computer programs or even on academic computer science research.
- Philip Greenspun, "We Have Chosen Shame and Will Get War."

I do remember one thing.
It took hours and hours,
But by the time I was done with it,
I was so involved,
I didn't know what to think.
I carried it around with me for days and days,
Playing little games,
Like not looking at it for a whole day,
And then looking at it,
To see if I still liked it.
I did!

- King Crimson, "Indiscipline", Discipline

I wish I had learned about decision trees in high school. Decision trees taught me to think. Decision trees are useful. Geometry is not.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 04 Aug 2013