David Eppstein - Publications

Publications with Boris Aronov

• On the number of minimal 1-Steiner trees.
  B. Aronov, M. Bern, and D. Eppstein.
  Disc. & Comp. Geom. 12: 29–34, 1994.

  Given a d-dimensional set of n points, the number of combinatorially different minimum spanning trees that can be formed by adding one more point is within a polylogarithmic factor of n^d.

• Distance-sensitive point location made easy.
  B. Aronov, M. De Berg, D. Eppstein, M. Roeloffzen, and B. Speckmann.
  30th European Workshop on Computational Geometry (EuroCG 2014), Dead Sea, Israel, March 2014.
  arXiv:1602.00767
  Comp. Geom. Theory & Applications 54: 17–31, 2016.

  We use quadtrees to handle point location queries in an amount of time that depends on the distance of the query point to the nearest region boundary.

• Better late than never: the complexity of arrangements of polyhedra.
  B. Aronov, S. W. Bae, O. Cheong, D. Eppstein, C. Knauer, and R. Seidel.
  41st European Workshop on Computational Geometry (EuroCG 2021), Liblice, Czech Republic, to appear.
  

Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.