David Eppstein - Publications

Publications with Leonidas J. Guibas

• The centroid of points with approximate weights.
  M. Bern, D. Eppstein, L. J. Guibas, J. Hershberger, S. Suri, and J. Wolter.
  3rd Eur. Symp. Algorithms, Corfu, 1995.
  Springer, Lecture Notes in Comp. Sci. 979, 1995, pp. 460–472.

  Given a set of points with weights that are not known precisely, but are known to fall within some range, considers the possible weighted centroids arising from different choices of weights in each range. The combinatorics of this problem are closely connected with those of zonotopes.

• Application Challenges to Computational Geometry.
  The Computational Geometry Impact Task Force Report.
  Tech. Rep. TR-521-96, Princeton University, April 1996.
  Advances in Discrete and Computational Geometry – Proc. 1996 AMS-IMS-SIAM Joint Summer Research Conf. Discrete and Computational Geometry: Ten Years Later, Contemporary Mathematics 223, Amer. Math. Soc., 1999, pp. 407–423.
  
• 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.