Jeff Erickson's Publications

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.

- Tom Magliozzi, "The Allegory of the Epiphany at the Fountain", a Car Talk Rant and Rave

		A near-optimal approximation algorithm for asymmetric TSP on embedded graphs with Anastasios Sidiropoulos Submitted to the 54th Annual IEEE Symposium on Foundations of Computer Science (2013).
		Efficiently hex-meshing things with topology To appear in Proceedings of the 29th Annual Symposium on Computational Geometry, 2013.
		Transforming curves on surfaces redux With Kim Whittlesey Proceedings of the 24rd Annual ACM-SIAM Symposium on Discrete Algorithms, 1646–1655, 2013.
		Multiple-source shortest paths in embedded graphs With Sergio Cabello and Erin W. Chambers To appear in SIAM Journal on Computing.
		Tracing compressed curves in triangulated surfaces With Amir Nayyeri* To appear in Discrete & Computational Geometry. Proceedings of the 28th Annual Symposium on Computational Geometry, 131–140, 2012.
		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.
		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)
		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* Submitted to Algorithmica, February 2012. Proceedings of the 12th Annual European Symposium on Algorithms, 160–171, 2006.
		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*. Proceedings of the 11th International Meshing Roundtable, 391–402, 2002. arXiv:cs.CG/0206002 Submitted for journal publication.
		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. Submitted for journal publication.
		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.

Jeff Erickson's Publications

Lecture notes, web pages, software, etc.