Jeff Erickson's Publications

Each paper title is a link to the abstract, publication history, copyright information, and electronic copies of that paper. Some of these pages are 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 made significant contributions to the paper as students. 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.

		🔥 FSM Builder: A tool for writing autograded finite automata questions> Eliot Wong Robson*, Samuel Ruggerio*, and Jeff Erickson. To appear in Proceedings of the 29th Annual ACM Conference on Innovation and Technology in Computer Science Education, 2024.
		Auto-graded scaffolding exercises for theoretical computer science With Jason Xia*, Eliot Wong Robson*, Tue Do*, Aidan Glickman*, Zhuofan Jia*, Eric Jin*, Jiwon Lee*, Patrick Lin*, Steven Pan*, Samuel Ruggerio*, Tomoko Sakurayama*, Andrew Yin*, Yael Gertner, and Brad Solomon. Proceedings of the 2023 ASEE Annual Conference and Exposition, 2023.
		Reconstructing graphs from connected triples With Paul Bastide*, Linda Cook, Carla Groenland, Marc van Kreveld, Isja Mannens*, and Jordi L. Vermeulen* Proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science, 16--29, 2023. Lecture Notes in Computer Science 14093, Springer. arXiv:2303.06609
		Minimum cuts in surface graphs With Erin Wolf Chambers*, Emily Kyle Fox*, and Amir Nayyeri* SIAM Journal on Computing 52(1):156–195, 2023. arXiv:1910.04278
		Planar and toroidal morphs made easier With Patrick Lin*, Journal of Graph Algorithms and Applications 27(2):95-118, 2023. (Special issue of invited papers from the 29th International Symposium on Graph Drawing and Network Visualization) arXiv:2106.14086
		Fusible numbers and Peano Arithmetic With Gabriel Nivasch and Junyan Xu* Logical Methods in Computer Science 18(3), 6:1–6:26, 2022. (Special issue of invited papers from the 36th Annual ACM/IEEE Symposium on Logic in Computer Science) LICS 2021 Distinguished Paper. arXiv:2003.14342
		Chasing puppies: Mobile beacon routing on closed curves With Mikkel Abrahamsen*, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen*, Jordi Vermeulen*, and Giovanni Viglietta*. Journal of Computational Geomettry 13(2):115--150, 2022. (Special issue of invited papers from the 37th International Symposium on Computational Geometry) arXiv:2103.09811
		How to morph graphs on the torus With Erin Wolf Chambers, Patrick Lin*, and Salman Parsa. Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms, 2759–2778, 2021. arXiv:2007.07927
		Smoothing the gap between NP and ∃ℝ With Ivor van der Hoog* and Tillmann Miltzow. 🔥SIAM Journal on Computing, 2022. (Special section of invited papers from the 61st Annual IEEE Symposium on Foundations of Computer Science) arXiv:1912.02278.
		A toroidal Maxwell–Cremona–Delaunay correspondence With Patrick Lin*. Journal of Computational Geomettry 12(2):55--85, 2021. (Special issue of invited papers from the 36th International Symposium on Computational Geometry) arXiv:2003.10057.
		Optimal curve straightening is ∃ℝ-complete Preprint, August 2019. arXiv:1908.09400
		Topologically trivial closed walks in directed surface graphs With Yipu Wang*. Discrete & Computational Geometry 64(4):1253–1294, 2020 (Special issue of invited papers from the 35th International Symposium on Computational Geometry) arXiv:1812.01564.
		Lower bounds for electrical reduction on surfaces With Hsien-Chih Chang* and Marcos Cossarini. Proceedings of the 35th International Symposium on Computational Geometry, 25:1–25:16, 2019. arXiv:1707.04683.
		Holiest minimum-cost paths and flows in surface graphs With Emily Kyle Fox and Luvsandondov Lkhamsuren*. Proceedings of the 50th Annual ACM Symposium on the Theory of Computing, 1319–1332, 2018. arXiv:1804.01045
		Four shortest vertex-disjoint paths in planar graphs With Yipu Wang*. Preprint, October 2017.
		Unfolding and dissection of multiple cubes With Zachary Abel*, Brad Ballinger, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg*, Hiro Ito, Irina Kostitsyna, Jayson Lynch*, and Ryuhei Uehara. Journal of Information Processing 25:610–615, 2017. (Special issue on discrete and computational geometry, graphs, and games)
		Recognizing weakly simple polygons With Hugo Akitaya*, Greg Aloupis, and Csaba Tóth Discrete & Computational Geometry 58(4):785–821, 2017. (Special issue of invited papers from the 32nd International Symposium on Computational Geometry) arXiv:1603.07401
		Untangling planar curves With Hsien-Chih Chang*. Discrete & Computational Geometry 58(4):889–920, 2017. (Special issue of invited papers from the 32nd International Symposium on Computational Geometry) arXiv:1702.00146 Winner of the SoCG 2016 Best Student Presentation award.
		Electrical reduction, homotopy moves, and defect With Hsien-Chih Chang*. Preprint, September 2015. arXiv:1510.00571. (Mostly superseded by Untangling planar curves and Lower bounds for electrical reduction on surfaces)
		Detecting weakly simple polygons With Hsien-Chih Chang* and Chao Xu*. Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms, 1655–1670, 2015.
		Efficiently hex-meshing things with topology Discrete & Computational Geometry 52(3):427–449, 2014. (Special issue of invited papers from the 29th Annual Symposium on Computational Geometry)
		A near-optimal approximation algorithm for asymmetric TSP on embedded graphs with Anastasios Sidiropoulos Proceedings of the 30th Annual Symposium on Computational Geometry, 130–135, 2014.
		Necklaces, convolutions, and X+Y With David Bremner, Timothy M. Chan, Erik D. Demaine, Ferran Hurtado, John Iacono, Mihai Pătraşcu, Stefan Langerman, and Perouz Taslakian* Algorithmica 69(2):294–314, 2014.
		Transforming curves on surfaces redux With Kim Whittlesey Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, 1646–1655, 2013.
		Multiple-source shortest paths in embedded graphs With Sergio Cabello and Erin Wolf Chambers SIAM Journal on Computing 42(4):1542–1571, 2013.
		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)
		Global minimum cuts in surface-embedded graphs With Emily Kyle Fox* and Amir Nayyeri* Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, 1309–1318, 2012.
		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.
		Shortest non-trivial cycles in directed surface graphs Proceedings of the 27th Annual Symposium on Computational Geometry, 236–243, 2011.
		Shortest non-crossing walks in the plane With Amir Nayyeri* Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 279–308, 2011.
		Computing replacement paths in surface-embedded graphs With Amir Nayyeri* Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 1347–1354, 2011.
		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.
		Computing the shortest essential cycle With Pratik Worah* Discrete & Computational Geometry 44(4):912–930, 2010.
		Maximum flows and parametric shortest paths in planar graphs Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, 794-804, 2010.
		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.
		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)
		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.
		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.)
		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.
		Empty-ellipse graphs With Xavier Goaoc and Olivier Devillers Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, 1249–1257, 2008.
		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)
		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)
		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.
		Tightening non-simple paths and cycles on surfaces With Éric Colin de Verdière SIAM Journal on Computing 39(8):3784–3813, 2010.
		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)
		Greedy optimal homotopy and homology generators With Kim Whittlesey Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 1038–1046, 2005.
		Lower bounds for external algebraic decision trees Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 755–761, 2005.
		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.
		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.
		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.
		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.
		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.
		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.
		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.
		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)
		Uniform samples of generic surfaces have nice Delaunay triangulations Preprint, December 2002.
		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.
		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
		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.
		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
		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
		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
		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
		Algorithmic issues in modeling motion by Pankaj K. Agarwal, Leonidas J. Guibas, and 19 others. ACM Computing Surveys 34(4):550–572, 2002.
		Dense point sets have sparse Delaunay triangulations Discrete & Computational Geometry 33:83–115, 2005.
		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
		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
		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
		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)
		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).
		Finding longest arithmetic progressions Manuscript, July 1999.
		Finite-resolution hidden surface removal Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, 901–909, 2000. arXiv:cs.CG/9910017
		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.
		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
		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)
		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)
		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.
		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.
		Space-time tradeoffs for emptiness queries SIAM Journal on Computing 29(6):1968–1996, 2000. Recent improvements!
		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".
		Lower Bounds for Fundamental Geometric Problems Ph.D. dissertation, University of California at Berkeley, July 1996.
		New lower bounds for convex hull problems in odd dimensions SIAM Journal on Computing 28(4):1198–1214, 1999.
		Sowing games Games of No Chance (Richard J. Nowakowski, editor), Mathematical Sciences Research Institute Publications 29, Cambridge University Press, 1996, pp. 287–297.
		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.
		On the relative complexities of some geometric problems Proceedings of the 7th Canadian Conference on Computational Geometry, 85–90, 1995.
		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!
		Lower bounds for linear satisfiability problems Chicago Journal of Theoretical Computer Science 1999(8), 1999.
		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.
		Iterated nearest neighbors and finding minimal polytopes With David Eppstein. Discrete & Computational Geometry 11(3):321–350, 1994.
		New algorithms for minimum measure simplices and one-dimensional weighted Voronoi diagrams With David Eppstein. U. C. Irvine Technical Report 92-55, June 1992.

• "TheorieLearn"
  Autograded scaffolding exercises for theoretical computer science classes at Illinois, on the PrairieLearn platform.

• Algorithms Course Materials
  Collected lecture notes, homeworks, and exams from UIUC's senior- and graduate-level algorithms classes. Revised January 2011.
  http://jeffe.cs.illinois.edu/teaching/algorithms/

• Computational Geometry Pages
  A comprehensive directory of computational geometry resources.
  http://jeffe.cs.illinois.edu/compgeom/

• biblook/bibindex
  Public domain software for indexing and searching BibTeX bibliographic databases.
  http://jeffe.cs.illinois.edu/biblook.html

• Plücker coordinates
  Ray Tracing News 10(3), 1997.
  Incorporated, with substantial revision by Ken Shoemake, in the comp.graphics.algorithms FAQ (Subject 6.09), edited by Joe O'Rourke.

• DrawPicture Data Format
  With Keith Rollin.
  Apple II GS Technical Note #46, November 1988.

• Font Family Numbers
  With Rilla Reynolds, and revised by Matt Deatherage and Keith Rollin.
  Apple II GS Technical Note #41, May 1988.

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." (1995)

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 (1981)