David Eppstein – Publications

Publications with Mark de Berg

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

• Covering many points with a small-area box.
  M. De Berg, S. Cabello, O. Cheong, D. Eppstein, and C. Knauer.
  arXiv:1612.02149.
  J. Computational Geometry 10 (1): 207–222, 2019.

  We give an efficient algorithm for finding the smallest axis-parallel rectangle covering a given number of points out of a larger set of points in the plane.