David Eppstein - Publications

Publications with David Dobkin

• Visibility with a moving point of view.
  M. Bern, D.P. Dobkin, D. Eppstein, and R. Grossman.
  1st ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1990, pp. 107–118.
  Algorithmica 11: 360–378, 1994.

  An investigation of 3d visibility problems in which the viewing position moves along a straight flight path, with various assumptions on the complexity of the viewed scene.

• Triangulating polygons without large angles.
  M. Bern, D. Dobkin, and D. Eppstein.
  8th ACM Symp. Comp. Geom., Berlin, 1992, pp. 222–231.
  Int. J. Comp. Geom. & Appl. 5: 171–192, 1995 (special issue for 8th Symp. Comput. Geom.)

  Follows up "Polynomial size non-obtuse triangulation of polygons"; improves the number of triangles by relaxing the requirements on their angles. Again mostly subsumed by results of Bern et al described in "Faster circle packing".

• Computing the discrepancy.
  D. P. Dobkin and D. Eppstein.
  9th ACM Symp. Comp. Geom., San Diego, 1993, pp. 47–52.

  Measures how well a sample of points from a set works as a discrete approximation to the continuous measure of shapes in the set, using algorithms based on Overmars and van Leeuwen's dynamic convex hull data structure. Some versions of the problem also involve subroutines for finding the deepest point in an arrangement of quadrants or orthants.

  This paper was merged with results of Mitchell to form the journal version, "Computing the discrepancy with applications to supersampling patterns".

• Computing the discrepancy with applications to supersampling patterns.
  D. P. Dobkin, D. Eppstein, and D. P. Mitchell.
  ACM Trans. on Graphics 15 (4): 354–376, 1996.

  Combines "Computing the discrepancy" with experimental results of Mitchell on the discrepancies of various point sets, emphasizing the application of low-discrepancy sets to anti-aliasing in raytraced graphics.

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