Jeff Erickson

According to our database, Jeff Erickson authored at least 106 papers between 1994 and 2023.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2023

Minimum Cuts in Surface Graphs.

Erin W. Chambers, Jeff Erickson, Kyle Fox, Amir Nayyeri

SIAM J. Comput., February, 2023

Planar and Toroidal Morphs Made Easier.

Jeff Erickson, Patrick Lin

J. Graph Algorithms Appl., 2023

Reconstructing Graphs from Connected Triples.

Paul Bastide, Linda Cook, Jeff Erickson, Carla Groenland, Marc J. van Kreveld, Isja Mannens, Jordi L. Vermeulen

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2023

2022

Fusible numbers and Peano Arithmetic.

Jeff Erickson, Gabriel Nivasch, Junyan Xu

Log. Methods Comput. Sci., 2022

The Tragedy of Being Almost but Not Quite Planar (Invited Talk).

Jeff Erickson

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

2021

A Toroidal Maxwell-Cremona-Delaunay Correspondence.

Jeff Erickson, Patrick Lin

J. Comput. Geom., 2021

How to Morph Graphs on the Torus.

Erin Wolf Chambers, Jeff Erickson, Patrick Lin, Salman Parsa

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Chasing Puppies: Mobile Beacon Routing on Closed Curves.

Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi L. Vermeulen, Giovanni Viglietta

Proceedings of the 37th International Symposium on Computational Geometry, 2021

2020

Topologically Trivial Closed Walks in Directed Surface Graphs.

Jeff Erickson, Yipu Wang

Discret. Comput. Geom., 2020

Smoothing the gap between NP and ER.

Jeff Erickson, Ivor van der Hoog, Tillmann Miltzow

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Chasing Puppies.

Jeff Erickson

Proceedings of the 32nd Canadian Conference on Computational Geometry, 2020

2019

Computational Geometry (Dagstuhl Seminar 19181).

Siu-Wing Cheng, Anne Driemel, Jeff Erickson

Dagstuhl Reports, 2019

A Framework for Robust Realistic Geometric Computations.

Jeff Erickson, Ivor van der Hoog, Tillmann Miltzow

CoRR, 2019

Optimal Curve Straightening is ∃R-Complete.

Jeff Erickson

CoRR, 2019

Lower Bounds for Electrical Reduction on Surfaces.

Hsien-Chih Chang, Marcos Cossarini, Jeff Erickson

Proceedings of the 35th International Symposium on Computational Geometry, 2019

Algorithms

Jeff Erickson

ISBN: 978-1-792-64483-2, 2019

2018

Holiest minimum-cost paths and flows in surface graphs.

Jeff Erickson, Kyle Fox, Luvsandondov Lkhamsuren

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Tightening Curves on Surfaces via Local Moves.

Hsien-Chih Chang, Jeff Erickson, David Letscher, Arnaud de Mesmay, Saul Schleimer, Eric Sedgwick, Dylan Thurston, Stephan Tillmann

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

Unfolding and Dissection of Multiple Cubes, Tetrahedra, and Doubly Covered Squares.

Zachary Abel, Brad Ballinger, Erik D. Demaine, Martin L. Demaine, Jeff Erickson, Adam Hesterberg, Hiro Ito, Irina Kostitsyna, Jayson Lynch, Ryuhei Uehara

J. Inf. Process., 2017

Untangling Planar Curves.

Hsien-Chih Chang, Jeff Erickson

Discret. Comput. Geom., 2017

Recognizing Weakly Simple Polygons.

Hugo A. Akitaya, Greg Aloupis, Jeff Erickson, Csaba D. Tóth

Discret. Comput. Geom., 2017

Computational Geometry (Dagstuhl Seminar 17171).

Otfried Cheong, Anne Driemel, Jeff Erickson

Dagstuhl Reports, 2017

Lower Bounds for Planar Electrical Reduction.

Hsien-Chih Chang, Jeff Erickson

CoRR, 2017

Embedded-width: A variant of treewidth for plane graphs.

Glencora Borradaile, Jeff Erickson, Hung Le, Robbie Weber

CoRR, 2017

2016

Global Minimum Cuts in Surface-Embedded Graphs.

Erin W. Chambers, Jeff Erickson, Kyle Fox, Amir Nayyeri

Encyclopedia of Algorithms, 2016

Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221).

Jeff Erickson, Philip N. Klein, Dániel Marx, Claire Mathieu

Dagstuhl Reports, 2016

2015

Computational Geometry (Dagstuhl Seminar 15111).

Otfried Cheong, Jeff Erickson, Monique Teillaud

Dagstuhl Reports, 2015

Electrical Reduction, Homotopy Moves, and Defect.

Hsien-Chih Chang, Jeff Erickson

CoRR, 2015

Detecting Weakly Simple Polygons.

Hsien-Chih Chang, Jeff Erickson, Chao Xu

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

Efficiently Hex-Meshing Things with Topology.

Jeff Erickson

Discret. Comput. Geom., 2014

Necklaces, Convolutions, and X+Y.

David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patrascu, Perouz Taslakian

Algorithmica, 2014

A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs.

Jeff Erickson, Anastasios Sidiropoulos

Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013

Multiple-Source Shortest Paths in Embedded Graphs.

Sergio Cabello, Erin W. Chambers, Jeff Erickson

SIAM J. Comput., 2013

Tracing Compressed Curves in Triangulated Surfaces.

Jeff Erickson, Amir Nayyeri

Discret. Comput. Geom., 2013

Transforming Curves on Surfaces Redux.

Jeff Erickson, Kim Whittlesey

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

Homology Flows, Cohomology Cuts.

Erin W. Chambers, Jeff Erickson, Amir Nayyeri

SIAM J. Comput., 2012

Global minimum cuts in surface embedded graphs.

Jeff Erickson, Kyle Fox, Amir Nayyeri

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Special Section on Foundations of Computer Science.

Scott Aaronson, Jeff Erickson, Mohammad Mahdian, R. Ravi, Emanuele Viola

SIAM J. Comput., 2011

Computing Replacement Paths in Surface Embedded Graphs.

Jeff Erickson, Amir Nayyeri

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Minimum Cuts and Shortest Non-Separating Cycles via Homology Covers.

Jeff Erickson, Amir Nayyeri

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Shortest Non-Crossing Walks in the Plane.

Jeff Erickson, Amir Nayyeri

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Shortest non-trivial cycles in directed surface graphs.

Jeff Erickson

Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

2010

Finding one tight cycle.

Sergio Cabello, Matt DeVos, Jeff Erickson, Bojan Mohar

ACM Trans. Algorithms, 2010

Tightening Nonsimple Paths and Cycles on Surfaces.

Éric Colin de Verdière, Jeff Erickson

SIAM J. Comput., 2010

Computing the Shortest Essential Cycle.

Jeff Erickson, Pratik Worah

Discret. Comput. Geom., 2010

Vietoris-Rips Complexes of Planar Point Sets.

Erin W. Chambers, Vin de Silva, Jeff Erickson, Robert Ghrist

Discret. Comput. Geom., 2010

Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time.

Erin W. Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, Shripad Thite

Comput. Geom., 2010

Maximum Flows and Parametric Shortest Paths in Planar Graphs.

Jeff Erickson

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009

Centerpoint Theorems for Wedges.

Jeff Erickson, Ferran Hurtado, Pat Morin

Discret. Math. Theor. Comput. Sci., 2009

Guest Editor's Foreword.

Jeff Erickson

Discret. Comput. Geom., 2009

Minimum cuts and shortest homologous cycles.

Erin W. Chambers, Jeff Erickson, Amir Nayyeri

Proceedings of the 25th ACM Symposium on Computational Geometry, 2009

2008

Realizing partitions respecting full and partial order information.

Erik D. Demaine, Jeff Erickson, Danny Krizanc, Henk Meijer, Pat Morin, Mark H. Overmars, Sue Whitesides

J. Discrete Algorithms, 2008

Splitting (complicated) surfaces is hard.

Erin W. Chambers, Éric Colin de Verdière, Jeff Erickson, Francis Lazarus, Kim Whittlesey

Comput. Geom., 2008

Empty-ellipse graphs.

Olivier Devillers, Jeff Erickson, Xavier Goaoc

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Walking your dog in the woods in polynomial time.

Erin W. Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, Shripad Thite

Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

Testing contractibility in planar rips complexes.

Erin W. Chambers, Jeff Erickson, Pratik Worah

Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

2007

Capturing a Convex Object With Three Discs.

Jeff Erickson, Shripad Thite, Fred Rothganger, Jean Ponce

IEEE Trans. Robotics, 2007

Finding Small Holes.

Jeff Erickson

Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

2006

On the Least Median Square Problem.

Jeff Erickson, Sariel Har-Peled, David M. Mount

Discret. Comput. Geom., 2006

Minimum-Cost Coverage of Point Sets by Disks

Esther M. Arkin, Hervé Brönnimann, Jeff Erickson, Sándor P. Fekete, Christian Knauer, Jonathan Lenchner, Joseph S. B. Mitchell, Kim Whittlesey

CoRR, 2006

Tightening non-simple paths and cycles on surfaces.

Éric Colin de Verdière, Jeff Erickson

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Necklaces, Convolutions, and <i>X</i> + <i>Y</i>.

David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Perouz Taslakian

Proceedings of the Algorithms, 2006

Minimum-cost coverage of point sets by disks.

Helmut Alt, Esther M. Arkin, Hervé Brönnimann, Jeff Erickson, Sándor P. Fekete, Christian Knauer, Jonathan Lenchner, Joseph S. B. Mitchell, Kim Whittlesey

Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

2005

Separating Point Sets in Polygonal Environments.

Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Mark H. Overmars, Sue Whitesides

Int. J. Comput. Geom. Appl., 2005

Building spacetime meshes over arbitrary spatial domains.

Jeff Erickson, Damrong Guoy, John M. Sullivan, Alper Üngör

Eng. Comput., 2005

Dense Point Sets Have Sparse Delaunay Triangulations or "... But Not Too Nasty".

Jeff Erickson

Discret. Comput. Geom., 2005

Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries.

David Bremner, Erik D. Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, Godfried T. Toussaint

Discret. Comput. Geom., 2005

Distance-2 Edge Coloring is NP-Complete

Jeff Erickson, Shripad Thite, David P. Bunde

CoRR, 2005

Local polyhedra and geometric graphs.

Jeff Erickson

Comput. Geom., 2005

Greedy optimal homotopy and homology generators.

Jeff Erickson, Kim Whittlesey

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Lower bounds for external algebraic decision trees.

Jeff Erickson

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004

Optimally Cutting a Surface into a Disk.

Jeff Erickson, Sariel Har-Peled

Discret. Comput. Geom., 2004

Kinetic collision detection between two simple polygons.

Julien Basch, Jeff Erickson, Leonidas J. Guibas, John Hershberger, Li Zhang

Comput. Geom., 2004

Automatic Blocking Scheme for Structured Meshing in 2d Multiphase Flow Simulation.

Damrong Guoy, Jeff Erickson

Proceedings of the 13th International Meshing Roundtable, 2004

Efficient Tradeoff Schemes in Data Structures for Querying Moving Objects.

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Hai Yu

Proceedings of the Algorithms, 2004

Spacetime meshing with adaptive refinement and coarsening.

Reza Abedi, Shuo-Heng Chung, Jeff Erickson, Yong Fan, Michael Garland, Damrong Guoy, Robert B. Haber, John M. Sullivan, Shripad Thite, Yuan Zhou

Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

2003

Indexing Moving Points.

Pankaj K. Agarwal, Lars Arge, Jeff Erickson

J. Comput. Syst. Sci., 2003

Nice Point Sets Can Have Nasty Delaunay Triangulations.

Jeff Erickson

Discret. Comput. Geom., 2003

Preprocessing chains for fast dihedral rotations is hard or even impossible.

Michael A. Soss, Jeff Erickson, Mark H. Overmars

Comput. Geom., 2003

On the Complexity of Halfspace Volume Queries.

Erik D. Demaine, Jeff Erickson, Stefan Langerman

Proceedings of the 15th Canadian Conference on Computational Geometry, 2003

2002

Flipping Cubical Meshes.

Marshall W. Bern, David Eppstein, Jeff Erickson

Eng. Comput., 2002

Flipturning Polygons.

Oswin Aichholzer, Carmen Cortés, Erik D. Demaine, Vida Dujmovic, Jeff Erickson, Henk Meijer, Mark H. Overmars, Belén Palop, Suneeta Ramaswami, Godfried T. Toussaint

Discret. Comput. Geom., 2002

Algorithmic issues in modeling motion.

Pankaj K. Agarwal, Leonidas J. Guibas, Herbert Edelsbrunner, Jeff Erickson, Michael Isard, Sariel Har-Peled, John Hershberger, Christian S. Jensen, Lydia E. Kavraki, Patrice Koehl, Ming C. Lin, Dinesh Manocha, Dimitris N. Metaxas, Brian Mirtich, David M. Mount, S. Muthukrishnan, Dinesh K. Pai, Elisha Sacks, Jack Snoeyink, Subhash Suri, Ouri Wolfson

ACM Comput. Surv., 2002

Flat-State Connectivity of Linkages under Dihedral Motions.

Greg Aloupis, Erik D. Demaine, Vida Dujmovic, Jeff Erickson, Stefan Langerman, Henk Meijer, Joseph O'Rourke, Mark H. Overmars, Michael A. Soss, Ileana Streinu, Godfried T. Toussaint

Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

Building Space-Time Meshes Over Arbitrary Spatial Domains.

Jeff Erickson, Damrong Guoy, John M. Sullivan, Alper Üngör

Proceedings of the 11th International Meshing Roundtable, 2002

Vertex-unfoldings of simplicial manifolds.

Erik D. Demaine, David Eppstein, Jeff Erickson, George W. Hart, Joseph O'Rourke

Proceedings of the 18th Annual Symposium on Computational Geometry, 2002

2001

Dense point sets have sparse Delaunay triangulations

Jeff Erickson

CoRR, 2001

Vertex-Unfoldings of Simplicial Polyhedra

Erik D. Demaine, David Eppstein, Jeff Erickson, George W. Hart, Joseph O'Rourke

CoRR, 2001

Reconfiguring convex polygons.

Oswin Aichholzer, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, Mark H. Overmars, Michael A. Soss, Godfried T. Toussaint

Comput. Geom., 2001

2000

Space-Time Tradeoffs for Emptiness Queries.

Jeff Erickson

SIAM J. Comput., 2000

Efficient Searching with Linear Constraints.

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo Giulio Franciosa, Jeffrey Scott Vitter

J. Comput. Syst. Sci., 2000

Finite-resolution hidden surface removal.

Jeff Erickson

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999

New Lower Bounds for Convex Hull Problems in Odd Dimensions.

Jeff Erickson

SIAM J. Comput., 1999

Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions.

David Eppstein, Jeff Erickson

Discret. Comput. Geom., 1999

Bounds for Linear Satisfiability Problems.

Jeff Erickson

Chic. J. Theor. Comput. Sci., 1999

Separation-Sensitive Collision Detection for Convex Objects.

Jeff Erickson, Leonidas J. Guibas, Jorge Stolfi, Li Zhang

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998

Kinetic Binary Space Partitions for Intersecting Segments and Disjoint Triangles (Extended Abstract).

Pankaj K. Agarwal, Jeff Erickson, Leonidas J. Guibas

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

1997

Erratum to Better Lower Bounds on Detecting Affine and Spherical Degeneracies.

Jeff Erickson, Raimund Seidel

Discret. Comput. Geom., 1997

Space-Time Tradeoffs for Emptiness Queries (Extended Abstract).

Jeff Erickson

Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

1996

New Lower Bounds for Hopcroft's Problem.

Jeff Erickson

Discret. Comput. Geom., 1996

Better Lower Bounds for Halfspace Emptiness.

Jeff Erickson

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

Better Lower Bounds on Detecting Affine and Spherical Degeneracies.

Jeff Erickson, Raimund Seidel

Discret. Comput. Geom., 1995

Lower Bounds for Linear Satisfiability Problems.

Jeff Erickson

Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

New Lower Bounds for Hopcroft's Problem (Extended Abstract).

Jeff Erickson

Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

On the relative complexities of some geometric problems.

Jeff Erickson

Proceedings of the 7th Canadian Conference on Computational Geometry, 1995

1994

Iterated Nearest Neighbors and Finding Minimal Polytopes.

David Eppstein, Jeff Erickson

Discret. Comput. Geom., 1994