David Eppstein - Publications

Publications with Shang-hua Teng

• A deterministic linear time algorithm for geometric separators and its applications.
  D. Eppstein, G.L. Miller, and S.-H. Teng.
  9th ACM Symp. Comp. Geom., San Diego, 1993, pp. 99–108.
  Fundamenta Informaticae 22: 309–330, 1995 (special issue on computational geometry).

  Teng and others previously showed that certain geometric graphs had small separators that could be found by lifting the graph to a sphere one dimension up and choosing a random great circle. Here we show that epsilon-cuttings and the method of conditional expectations can be used to guide a deterministic prune-and-search method for the same problem. Applications include finding the intersection graph of a collection of spheres and computing or approximating the maximum number of spheres having a common intersection.

• Approximating center points with iterated Radon points.
  K. Clarkson, D. Eppstein, G.L. Miller, C. Sturtivant, and S.-H. Teng.
  9th ACM Symp. Comp. Geom., San Diego, 1993, pp. 91–98.
  Int. J. Comp. Geom. & Appl. 6 (3): 357–377, 1996.

  Given a collection of n sites, a center point is a point (not necessarily a site) such that no hyperplane through the centerpoint partitions the collection into a very small and a very large subset. Center points have been used by Teng and others as a key step in the construction of geometric separators. One can find a point with this property by choosing a random sample of the collection and applying linear programming, but the complexity of that method grows exponentially with the dimension. This paper proposes an alternate method that produces lower quality approximations (in terms of the size of the worst hyperplane partition) but takes time polynomial in both n and d.

• Parallel construction of quadtrees and quality triangulations.
  M. Bern, D. Eppstein, and S.-H. Teng.
  3rd Worksh. Algorithms and Data Structures, Montreal, 1993.
  Springer, Lecture Notes in Comp. Sci. 709, 1993, pp. 188–199.
  Tech. Rep. 614, MIT Lab. for Comp. Sci., 1994.
  Int. J. Comp. Geom. & Appl. 9 (6): 517–532, 1999.

  A parallelization of the quadtree constructions in "Provably good mesh generation", in an integer model of computation, based on a technique of sorting the input points using values formed by shuffling the binary representations of the coordinates. A side-effect is an efficient construction for the "fair split tree" hierarchical clustering method used by Callahan and Kosaraju for various nearest neighbor problems.

• Regression depth and center points.
  N. Amenta, M. Bern, D. Eppstein, and S.-H. Teng.
  arXiv:cs.CG/9809037.
  3rd CGC Worksh. Computational Geometry, Brown Univ., 1998.
  Disc. Comp. Geom. 23 (3): 305–323, 2000.

  We show that, for any set of n points in d dimensions, there exists a hyperplane with regression depth at least ceiling(n/(d+1)). as had been conjectured by Rousseeuw and Hubert. Dually, for any arrangement of n hyperplanes in d dimensions there exists a point that cannot escape to infinity without crossing at least ceiling(n/(d+1)) hyperplanes. We also apply our approach to related questions on the existence of partitions of the data into subsets such that a common plane has nonzero regression depth in each subset, and to the computational complexity of regression depth problems.