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

		Minimum cuts and shortest homologous cycles Written with Erin Wolf Chambers and Amir Nayyeri* Submitted to the 25th Annual Symposium on Computational Geometry (2009)
		Homology flows, cohomology cuts Written with Erin Wolf Chambers and Amir Nayyeri* Submitted to the 41st ACM Symposium on Theory of Computing (2009)
		Computing the shortest essential cycle Written with Pratik Worah* Preprint, July 2008.
		Testing contractibility in planar Rips complexes Written 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 Written with Erin Wolf Chambers*, Éric Colin de Verdière, Sylvain Lazard, Francis Lazarus, and Shripad Thite Proccedings of the 24th Annual ACM Symposium on Computational Geometry, 101-109, 2008.
		Rips complexes of planar point sets Written with Erin Wolf Chambers*, Vin de Silva, and Robert Ghrist Preprint, December 2007. ArXiv:0712.0395.
		Empty-ellipse graphs Written with Xavier Goaoc and Olivier Devillers Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, 1249-1257, 2008.
		Finding one tight cycle Written with Sergio Cabello, Matt DeVos, and Bojan Mohar Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, 527-531, 2008.
		Necklaces, convolutions, and X+Y Written with David Bremner, Timothy M. Chan, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, Ileana Streinu, and Perouz Taslakian* Proceedings of the 12th Annual European Symposium on Algorithms, 160-171, 2006.
		Splitting (complicated) surfaces is hard Written with Erin Wolf Chambers*, Éric Colin de Verdière, Francis Lazarus, and Kim Whittlesey Proceedings of the 22nd Annual ACM Symposium on Computational Geometry, 421-429, 2006.
		Minimum-cost coverage of point sets by disks Written 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 Written with Éric Colin de Verdière Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 192-201, 2006.
		Realizing partitions respecting full and partial order information Written 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 Written 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 Written 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 Written with Damrong Guoy Proceedings of the 13th Annual International Meshing Roundtable, 121--132, 2004.
		Spacetime meshing with adaptive refinement and coarsening Written 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 Written 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 Written 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 Written 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 Written 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 Written 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 Written 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 Written 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 Written 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 Written 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 Written 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 Written 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 Written 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 Written 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 Written 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 Written 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 Written with Julien Basch, Leonidas J. Guibas, John Hershberger, and Li Zhang. Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 102-111, 1999. Computational Geometry: Theory and Applications 27:211-235, 2004.
		Separation-sensitive collision detection for convex objects Written 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 Written 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 Written 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 Written 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 Written 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 In 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 In 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 Written 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 Written with David Eppstein. Discrete & Computational Geometry 11(3):321-350, 1994.
		New algorithms for minimum measure simplices and one-dimensional weighted Voronoi diagrams Written with David Eppstein. U. C. Irvine Technical Report 92-55, June 1992.

Jeff Erickson's Publications

Lecture notes, web pages, software, etc.