David Eppstein - Publications

Publications with Paul Plassman

• Horizon theorems for lines and polygons.
  M. Bern, D. Eppstein, P. Plassman, and F. Yao.
  Discrete and Computational Geometry: Papers from the DIMACS Special Year, J. Goodman, R. Pollack, and W. Steiger, eds.,
  DIMACS Series in Discrete Mathematics and Theoretical Computer Science 6, Amer. Math. Soc., 1991, 45–66.

  The total complexity of the cells in a line arrangement that are cut by another line is at most \(15n/2\). The complexity of cells cut by a convex \(k\)-gon is \(O(n\alpha(n,k))\). The first bound is tight, but it remains open whether the second is, or whether only linear complexity is possible.

• Emerging challenges in computational topology.
  M. Bern, D. Eppstein, et al.
  arXiv:cs.CG/9909001.
  

  This is the report from the ACM Workshop on Computational Topology run by Marshall and myself in Miami Beach, June 1999. It details goals, current research, and recommendations in this emerging area of collaboration between computer science and mathematics.