David Eppstein – Publications

Publications with Scott Mitchell

• Edge insertion for optimal triangulations.
  M. Bern, H. Edelsbrunner, D. Eppstein, S. Mitchell, and T.S. Tan.
  1st Latin Amer. Symp. Theoretical Informatics, Sao Paulo, 1992.
  Springer, Lecture Notes in Comp. Sci. 583, 1992, pp. 46–60.
  Tech. Rep. EDC UILU-ENG-92-1702, Univ. Illinois, Urbana-Champaign, 1992.
  Disc. & Comp. Geom. 10: 47–65, 1993.

  One standard way of constructing Delaunay triangulations is by iterated local improvement, in which each step flips the diagonal of some quadrilateral. For many other optimal triangulation problems, flipping is insufficient, but the problems can instead be solved by a more general local improvement step in which a new edge is added to the triangulation, cutting through several triangles, and the region it cuts through is retriangulated on both sides.