David Eppstein – Publications

Publications with Pankaj Agarwal

• Dynamic algorithms for half-space reporting, proximity problems, and geometric minimum spanning trees.
  P.K. Agarwal, D. Eppstein, and J. Matoušek.
  33rd IEEE Symp. Foundations of Comp. Sci., Pittsburgh, 1992, pp. 80–89.

  This conference paper merged my results from "Dynamic Euclidean minimum spanning trees" with results of my co-authors on nearest neighbors and halfspace range searching.

• Parametric and kinetic minimum spanning trees.
  P. K. Agarwal, D. Eppstein, L. J. Guibas, and M. R. Henzinger.
  39th IEEE Symp. Foundations of Comp. Sci., 1998, pp. 596–605..

  We describe algorithms for maintaining the minimum spanning tree in a graph in which the edge weights are piecewise linear functions of time that may change unpredictably. We solve the problem in time O(n^2/3 polylog n) per combinatorial change to the tree for general graphs, and in time O(n^1/4 polylog n) per combinatorial change to the tree for planar graphs.

  (FOCS '98 talk slides)

• 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.