Jeff Erickson

Christian Howard

Proceedings of the 41st International Symposium on Computational Geometry, 2025

2024

A Survey of Undergraduate Theory of Computation Curricula in the United States.

[BibT_eX]

[DOI]

Proceedings of the 2024 Working Group Reports on 1st ACM Virtual Global Computing Education Conference, 2024

A Survey of Undergraduate Theory of Computing Curricula.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM Virtual Global Computing Education Conference V. 2, 2024

FSM Builder: A Tool for Writing Autograded Finite Automata Questions.

[BibT_eX]

[DOI]

Eliot Wong Robson

Sam Ruggerio

Proceedings of the 2024 on Innovation and Technology in Computer Science Education V. 1, 2024

2023

Minimum Cuts in Surface Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., February, 2023

Reconstructing Graphs from Connected Triples.

[BibT_eX]

[DOI]

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

2022

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

[BibT_eX]

[DOI]

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

2021

How to Morph Graphs on the Torus.

[BibT_eX]

[DOI]

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

Fusible numbers and Peano Arithmetic.

[BibT_eX]

[DOI]

Gabriel Nivasch

Junyan Xu

Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

Planar and Toroidal Morphs Made Easier.

[BibT_eX]

[DOI]

Patrick Lin

Proceedings of the Graph Drawing and Network Visualization - 29th International Symposium, 2021

Chasing Puppies: Mobile Beacon Routing on Closed Curves.

[BibT_eX]

[DOI]

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

2020

Smoothing the gap between NP and ER.

[BibT_eX]

[DOI]

Ivor van der Hoog

Tillmann Miltzow

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

A Toroidal Maxwell-Cremona-Delaunay Correspondence.

[BibT_eX]

[DOI]

Patrick Lin

Proceedings of the 36th International Symposium on Computational Geometry, 2020

Chasing Puppies.

[BibT_eX]

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

2019

Computational Geometry (Dagstuhl Seminar 19181).

[BibT_eX]

[DOI]

Siu-Wing Cheng

Anne Driemel

Dagstuhl Reports, 2019

A Framework for Robust Realistic Geometric Computations.

[BibT_eX]

[DOI]

Ivor van der Hoog

Tillmann Miltzow

CoRR, 2019

Optimal Curve Straightening is ∃R-Complete.

[BibT_eX]

[DOI]

CoRR, 2019

Lower Bounds for Electrical Reduction on Surfaces.

[BibT_eX]

[DOI]

Marcos Cossarini

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

Topologically Trivial Closed Walks in Directed Surface Graphs.

[BibT_eX]

[DOI]

Yipu Wang

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

Algorithms

[BibT_eX]

[DOI]

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

2018

Holiest minimum-cost paths and flows in surface graphs.

[BibT_eX]

[DOI]

Kyle Fox

Luvsandondov Lkhamsuren

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

Tightening Curves on Surfaces via Local Moves.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

J. Inf. Process., 2017

Computational Geometry (Dagstuhl Seminar 17171).

[BibT_eX]

[DOI]

Otfried Cheong

Anne Driemel

Dagstuhl Reports, 2017

Lower Bounds for Planar Electrical Reduction.

[BibT_eX]

[DOI]

CoRR, 2017

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

[BibT_eX]

[DOI]

CoRR, 2017

2016

Global Minimum Cuts in Surface-Embedded Graphs.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

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

[BibT_eX]

[DOI]

Dagstuhl Reports, 2016

Untangling Planar Curves.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

Recognizing Weakly Simple Polygons.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015

Computational Geometry (Dagstuhl Seminar 15111).

[BibT_eX]

[DOI]

Otfried Cheong

Monique Teillaud

Dagstuhl Reports, 2015

Electrical Reduction, Homotopy Moves, and Defect.

[BibT_eX]

[DOI]

CoRR, 2015

Detecting Weakly Simple Polygons.

[BibT_eX]

[DOI]

Chao Xu

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

2014

Necklaces, Convolutions, and X+Y.

[BibT_eX]

[DOI]

Algorithmica, 2014

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

[BibT_eX]

[DOI]

Anastasios Sidiropoulos

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

2013

Multiple-Source Shortest Paths in Embedded Graphs.

[BibT_eX]

[DOI]

Sergio Cabello

SIAM J. Comput., 2013

Transforming Curves on Surfaces Redux.

[BibT_eX]

[DOI]

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

Efficiently hex-meshing things with topology.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Computational Geometry 2013, 2013

2012

Global minimum cuts in surface embedded graphs.

[BibT_eX]

[DOI]

Kyle Fox

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

Tracing compressed curves in triangulated surfaces.

[BibT_eX]

[DOI]

Proceedings of the 28th ACM Symposium on Computational Geometry, 2012

2011

Special Section on Foundations of Computer Science.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Computing Replacement Paths in Surface Embedded Graphs.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

Shortest Non-Crossing Walks in the Plane.

[BibT_eX]

[DOI]

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

Shortest non-trivial cycles in directed surface graphs.

[BibT_eX]

[DOI]

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

2010

Tightening Nonsimple Paths and Cycles on Surfaces.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

Computing the Shortest Essential Cycle.

[BibT_eX]

[DOI]

Pratik Worah

Discret. Comput. Geom., 2010

Vietoris-Rips Complexes of Planar Point Sets.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2010

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

[BibT_eX]

[DOI]

Comput. Geom., 2010

Maximum Flows and Parametric Shortest Paths in Planar Graphs.

[BibT_eX]

[DOI]

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

2009

Centerpoint Theorems for Wedges.

[BibT_eX]

[DOI]

Ferran Hurtado

Pat Morin

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

Guest Editor's Foreword.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2009

Homology flows, cohomology cuts.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Minimum cuts and shortest homologous cycles.

[BibT_eX]

[DOI]

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

2008

Realizing partitions respecting full and partial order information.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2008

Empty-ellipse graphs.

[BibT_eX]

[DOI]

Olivier Devillers

Xavier Goaoc

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

Finding one tight cycle.

[BibT_eX]

[DOI]

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

Walking your dog in the woods in polynomial time.

[BibT_eX]

[DOI]

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

Testing contractibility in planar rips complexes.

[BibT_eX]

[DOI]

Pratik Worah

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

2007

Finding Small Holes.

[BibT_eX]

[DOI]

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

2006

Minimum-Cost Coverage of Point Sets by Disks

[BibT_eX]

[DOI]

Joseph S. B. Mitchell

CoRR, 2006

Tightening non-simple paths and cycles on surfaces.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2006

Splitting (complicated) surfaces is hard.

[BibT_eX]

[DOI]

Francis Lazarus

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

Minimum-cost coverage of point sets by disks.

[BibT_eX]

[DOI]

Joseph S. B. Mitchell

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

2005

Building spacetime meshes over arbitrary spatial domains.

[BibT_eX]

[DOI]

Eng. Comput., 2005

Distance-2 Edge Coloring is NP-Complete

[BibT_eX]

[DOI]

Shripad Thite

David P. Bunde

CoRR, 2005

Greedy optimal homotopy and homology generators.

[BibT_eX]

[DOI]

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

Lower bounds for external algebraic decision trees.

[BibT_eX]

[DOI]

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

2004

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

[BibT_eX]

[DOI]

Damrong Guoy

Proceedings of the 13th International Meshing Roundtable, 2004

Efficient Tradeoff Schemes in Data Structures for Querying Moving Objects.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2004

On the least median square problem.

[BibT_eX]

[DOI]

Sariel Har-Peled

David M. Mount

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

Separating point sets in polygonal environments.

[BibT_eX]

[DOI]

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

Spacetime meshing with adaptive refinement and coarsening.

[BibT_eX]

[DOI]

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

2003

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

[BibT_eX]

[DOI]

Michael A. Soss

Mark H. Overmars

Comput. Geom., 2003

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

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 8th International Workshop, 2003

Capturing a convex object with three discs.

[BibT_eX]

[DOI]

Proceedings of the 2003 IEEE International Conference on Robotics and Automation, 2003

Local polyhedra and geometric graphs.

[BibT_eX]

[DOI]

Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

On the Complexity of Halfspace Volume Queries.

[BibT_eX]

[DOI]

Erik D. Demaine

Stefan Langerman

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

2002

Flipping Cubical Meshes.

[BibT_eX]

[DOI]

Marshall W. Bern

David Eppstein

Eng. Comput., 2002

Flipturning Polygons.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2002

Algorithmic issues in modeling motion.

[BibT_eX]

[DOI]

ACM Comput. Surv., 2002

Dense point sets have sparse Delaunay triangulations: or "... but not too nasty".

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Flat-State Connectivity of Linkages under Dihedral Motions.

[BibT_eX]

[DOI]

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

Building Space-Time Meshes Over Arbitrary Spatial Domains.

[BibT_eX]

[DOI]

Proceedings of the 11th International Meshing Roundtable, 2002

Optimally cutting a surface into a disk.

[BibT_eX]

[DOI]

Sariel Har-Peled

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

Vertex-unfoldings of simplicial manifolds.

[BibT_eX]

[DOI]

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

2001

Dense point sets have sparse Delaunay triangulations

[BibT_eX]

[DOI]

CoRR, 2001

Vertex-Unfoldings of Simplicial Polyhedra

[BibT_eX]

[DOI]

CoRR, 2001

Nice point sets can have nasty Delaunay triangulations.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001

2000

Space-Time Tradeoffs for Emptiness Queries.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

Finite-resolution hidden surface removal.

[BibT_eX]

[DOI]

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

Indexing Moving Points.

[BibT_eX]

[DOI]

Pankaj K. Agarwal

Lars Arge

Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2000

Reconfiguring Convex Polygons.

[BibT_eX]

[DOI]

Proceedings of the 12th Canadian Conference on Computational Geometry, 2000

1999

Bounds for Linear Satisfiability Problems.

[BibT_eX]

[DOI]

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

Separation-Sensitive Collision Detection for Convex Objects.

[BibT_eX]

[DOI]

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

Kinetic Collision Detection Between Two Simple Polygons.

[BibT_eX]

[DOI]

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).

[BibT_eX]

[DOI]

Pankaj K. Agarwal

Leonidas J. Guibas

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

Efficient Searching with Linear Constraints.

[BibT_eX]

[DOI]

Pankaj K. Agarwal

Lars Arge

Paolo Giulio Franciosa

Jeffrey Scott Vitter

Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1998

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

[BibT_eX]

[DOI]

David Eppstein

Proceedings of the Fourteenth Annual Symposium on Computational Geometry, 1998

1997

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

[BibT_eX]

Raimund Seidel

Discret. Comput. Geom., 1997

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

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

1996

New Lower Bounds for Hopcroft's Problem.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 1996

Better Lower Bounds for Halfspace Emptiness.

[BibT_eX]

[DOI]

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

New Lower Bounds for Convex Hull Problems in Odd Dimensions.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

1995

Lower Bounds for Linear Satisfiability Problems.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

On the relative complexities of some geometric problems.

[BibT_eX]

[DOI]

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

1993

Iterated Nearest Neighbors and Finding Minimal Polytopes.

[BibT_eX]

[DOI]

David Eppstein

Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

Better Lower Bounds on Detecting Affine and Spherical Degeneracies

[BibT_eX]

[DOI]