David Eppstein - Publications

Publications with Jeff Erickson

• New algorithms for minimum measure simplices and one-dimensional weighted Voronoi diagrams.
  D. Eppstein and J. Erickson.
  Tech. Rep. 92-55, ICS, UCI, 1992.

  Looks at space complexity of finding minimum simplices – solves the problem in O(n²) space and O(n^d) time (matching the best known time bounds) or in linear space at the expense of an additional log in time. Also finds one-dimensional multiplicatively weighted Voronoi diagrams in linear time for sorted inputs (O(n log n) was known).

• Iterated nearest neighbors and finding minimal polytopes.
  D. Eppstein and J. Erickson.
  Tech. Rep. 92-71, ICS, UCI, 1992.
  4th ACM-SIAM Symp. Discrete Algorithms, Austin, 1993, pp. 64–73.
  Disc. Comp. Geom. 11: 321–350, 1994.

  Showed that for various optimization criteria, the optimal polygon containing k of n points must be near one of the points, hence one can transform time bounds involving several factors of n to bounds linear in n but polynomial in k. Used as a subroutine are data structures for finding several nearest neighbors in rectilinear metric spaces, and algorithms for finding the deepest point in an arrangement of cubes or spheres.

• Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions.
  D. Eppstein and J. Erickson.
  14th ACM Symp. Comp. Geom., Minneapolis, 1998, pp. 58–67.
  Disc. Comp. Geom. 22 (4): 569–592, 1999 (special issue for SCG 1998).

  We use my dynamic closest pair data structure from "Dynamic Euclidean minimum spanning trees" to detect collisions among a collection of moving objects in sublinear time per collision. As one application, we can construct the straight skeleton of Aichholzer et al (and the mitered offset curves from which it is defined) in subquadratic time.

• Vertex-unfoldings of simplicial manifolds.
  E. Demaine, D. Eppstein, J. Erickson, G. Hart, and J. O'Rourke.
  Tech. Reps. 071 and 072, Smith College, 2001.
  arXiv:cs.CG/0107023 and cs.CG/0110054.
  18th ACM Symp. Comp. Geom., Barcelona, 2002, pp. 237–243.
  Discrete Geometry: In honor of W. Kuperberg's 60th birthday, Pure and Appl. Math. 253, Marcel Dekker, pp. 215–228, 2003.

  We unfold any polyhedron with triangular faces into a planar layout in which the triangles are disjoint and are connected in a sequence from vertex to vertex

  (Jeff's pubs page)

• Flipping cubical meshes.
  M. Bern D. Eppstein, and J. Erickson.
  arXiv:cs.CG/0108020.
  10th Int. Meshing Roundtable, Newport Beach, 2001, pp. 19–29.
  Engineering with Computers 18 (3): 173–187, 2002.

  We examine flips in which a set of mesh cells connected in a similar pattern to a subset of faces of a cube or hypercube is replaced by cells in the pattern of the complementary subset. We show that certain flip types preserve geometric realizability of a mesh, and use this to study the question of whether every topologically meshable domain is geometrically meshable. We also study flip graph connectivity, and prove that the flip graph of quadrilateral meshes has exactly two connected components.

  Note that the Meshing Roundtable version was by Bern and Eppstein. Erickson was added as a co-author during the revisions for the journal version.

  (Slides)