

Holiest minimumcost paths and flows in surface graphs
With Kyle Fox and
Luvsandondov Lkhamsuren*.
To appear in Proceedings of the 50th Annual ACM Symposium on the Theory of Computing, 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)



Lower bounds for planar electrical reduction
With HsienChih Chang*.
Preprint, July 2017.
arXiv:1707.04683.



Recognizing weakly simple polygons
With
Hugo Akitaya*,
Greg Aloupis,
and Csaba Tó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)



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.
