

Fusible numbers and Peano Arithmetic
With
Gabriel Nivasch
and
Junyan Xu*
π₯To appear in Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021.
arXiv:2003.14342



π₯Chasing puppies: Mobile beacon routing on closed curves
With
Mikkel Abrahamsen*,
Irina Kostitsyna,
Maarten LoΜffler,
Tillmann Miltzow,
JeΜroΜme Urhausen*,
Jordi Vermeulen*, and
Giovanni Viglietta*.
To appear in Proceedings of the 37th International Symposium on Computational Geometry, 2021.
π₯arXiv:2103.09811



How to morph graphs on the torus
With
Erin Wolf Chambers,
Patrick Lin*,
and Salman Parsa.
π₯Proceedings of the 32nd ACMSIAM Symposium on Discrete Algorithms, 2759β2778, 2021.
arXiv:2007.07927



Smoothing the gap between NP and ββ
With Ivor van der Hoog*
and Tillmann Miltzow.
Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science, 10221033, 2020.
arXiv:1912.02278.



A toroidal MaxwellβCremonaβDelaunay correspondence
With Patrick Lin*.
Proceedings of the 36th International Symposium on Computational Geometry, 40:1β40:17, 2020.
Full version invited and submitted to the special issue of Journal of Computational Geomettry devoted to the conference.
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
HsienChih Chang*
and
Marcos Cossarini.
Proceedings of the 35th International Symposium on Computational Geometry, 25:1β25:16, 2019.
Preliminary version (without Cossarini) in arXiv:1707.04683.



Holiest minimumcost paths and flows in surface graphs
With 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 vertexdisjoint 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 of discrete and computational geometry, graphs, and games)



Recognizing weakly simple polygons
With
Hugo Akitaya*,
Greg Aloupis,
and Csaba ToΜ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 HsienChih 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 HsienChih 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 HsienChih Chang*
and Chao Xu*.
Proceedings of the 26th ACMSIAM Symposium on Discrete Algorithms, 1655β1670, 2015.



Efficiently hexmeshing 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 nearoptimal 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.
Proceedings of the 12th Annual European Symposium on Algorithms, 160β171, 2006.



Transforming curves on surfaces redux
With
Kim Whittlesey
Proceedings of the 24th Annual ACMSIAM Symposium on Discrete Algorithms, 1646β1655, 2013.



Multiplesource shortest paths in embedded graphs
With
Sergio Cabello
and
Erin W. 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 surfaceembedded graphs
With
Kyle Fox* and
Amir Nayyeri*
Proceedings of the 23rd Annual ACMSIAM 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 nontrivial cycles in directed surface graphs
Proceedings of the 27th Annual Symposium on Computational Geometry, 236β243, 2011.



Shortest noncrossing walks in the plane
With Amir Nayyeri*
Proceedings of the 22nd Annual ACMSIAM Symposium on Discrete Algorithms, 279β308, 2011.



Computing replacement paths in surfaceembedded graphs
With Amir Nayyeri*
Proceedings of the 22nd Annual ACMSIAM Symposium on Discrete Algorithms, 1347β1354, 2011.



Minimum cuts and shortest nonseparating cycles via homology covers
With Amir Nayyeri*
Proceedings of the 22nd Annual ACMSIAM 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 ACMSIAM Symposium on Discrete Algorithms, 794804, 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.)



VietorisRips complexes of planar point sets
With
Erin Wolf Chambers*,
Vin de Silva,
and
Robert Ghrist
Discrete & Computational Geometry 44(1):75β90, 2010.



Emptyellipse graphs
With
Xavier Goaoc
and
Olivier Devillers
Proceedings of the
19th Annual ACMSIAM 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 ACMSIAM 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)



Minimumcost 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 nonsimple 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 ACMSIAM
Symposium on Discrete Algorithms, 1038β1046, 2005.



Lower bounds for external algebraic decision trees
Proceedings of the
16th Annual ACMSIAM
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*,
ShuoHeng 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 HarPeled 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.



Outputsensitive algorithms for computing nearestneighbor 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



Flatstate 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 HarPeled.
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



Vertexunfoldings 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 3polytopes
With Scott Kim.
Discrete Geometry: In Honor of
W. Kuperberg's
60th Birthday
(András Bezdek,
editor), MarcelDekker, 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.



Finiteresolution hidden surface removal
Proceedings of the
11th Annual ACMSIAM 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.



Separationsensitive collision detection for convex objects
With
Leonidas J. Guibas,
Jorge Stolfi, and
Li Zhang*.
Proceedings of the 10th Annual
ACMSIAM 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
ACMSIAM 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.



Spacetime 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 "Spacetime 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 onedimensional weighted Voronoi diagrams
With David Eppstein.
U. C. Irvine Technical Report 9255, June 1992.
