David Eppstein - Publications

Journal of Computing and Systems Sciences

• Provably good mesh generation.
  M. Bern, D. Eppstein, and J. Gilbert.
  31st IEEE Symp. Foundations of Comp. Sci., St. Louis, Missouri, 1990, pp. 231-241.
  J. Comp. Sys. Sci. 48:384-409, 1994 (special issue for 31st FOCS).

  Uses quadtrees to construct triangulations with extra Steiner vertices added to the original input. Triangulates planar point sets and polygons, with all angles bounded away from zero, using a number of triangles within a constant of optimal. Triangulates planar point sets with all angles non-obtuse, using linearly many triangles. Triangulates higher dimensional point sets with no small solid angles and a number of simplices within a constant of optimal. Augments any higher dimensional point set so the Delaunay triangulation has linear complexity.

  (BibTeX -- Citations -- Preliminary copy of journal version -- MIT hypertext bibliography -- CiteSeer -- ACM DL (JCSS))

• Separator based sparsification I: planarity testing and minimum spanning trees.
  D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.
  J. Comp. Sys. Sci. 52:3-27, 1996 (special issue for 25th STOC).

  First half of journal version of Separator based sparsification for dynamic planar graph algorithms.

  (Citations -- ACM DL)

• Guest editor's forward to special issue of papers from the 34th Annual Symposium on Foundations of Computer Science.
  D. Eppstein.
  J. Comp. Sys. Sci. 54:263, 1997.

  (BibTeX)

Journals -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine

Semi-automatically filtered from a common source file.