David Eppstein - Publications

Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG³)

• Forbidden configurations in discrete geometry.
  D. Eppstein.
  Paul Erdős Memorial Lecture, 29th Canadian Conference on Computational Geometry, Ottawa, Canada, 2017.
  Invited talk, 20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Tokyo, 2017.
  Invited talk, 5th International Combinatorics Conference, Melbourne, Australia, 2017.
  Invited talk, Southern California Theory Day, Irvine, California, 2018.
  Cambridge University Press, 2018.

  We survey problems on finite sets of points in the Euclidean plane that are monotone under removal of points and depend only on the order-type of the points, and the subsets of points (forbidden configurations) that prevent a point set from having a given monotone property.

  (CCCG talk slides – CCCG talk video – SCTD talk slides – Updates, errata, and reviews)

• Stable-matching Voronoi diagrams.
  D. Eppstein.
  Invited talk at 21st Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG³), Manila, Philippines, 2018.
  

  We survey the results from several of my earlier papers: Algorithms for stable matching and clustering in a grid, Defining equitable geographic districts in road networks via stable matching, Reactive proximity data structures for graphs, and Stable-matching Voronoi diagrams: combinatorial complexity and algorithms.

  (Slides)

• Ununfoldable Polyhedra with 6 Vertices or 6 Faces.
  H. A. Akitaya, E. Demaine, D. Eppstein, T. Tachi, and R. Uehara.
  22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG³), Tokyo, Japan, 2019, pp. 27–28.
  Comp. Geom. Theory & Applications 103: 101857, 2022.
  

  We find a (nonconvex, but topologically equivalent to convex) polyhedron with seven vertices and six faces that cannot be unfolded to a flat polygon by cutting along its edges. Both the number of vertices and the number of faces are the minimum possible. The JCDCG³ version used the title "Minimal ununfoldable polyhedron".

Conferences – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.