David Eppstein – Publications

Publications with Frances Yao

Horizon theorems for lines and polygons.
M. Bern, D. Eppstein, P. Plassman, and F. Yao.
Discrete and Computational Geometry: Papers from the DIMACS Special Year, J. Goodman, R. Pollack, and W. Steiger, eds.,
DIMACS Series in Discrete Mathematics and Theoretical Computer Science 6, Amer. Math. Soc., 1991, 45–66.

The total complexity of the cells in a line arrangement that are cut by another line is at most \(15n/2\). The complexity of cells cut by a convex \(k\)-gon is \(O(n\alpha(n,k))\). The first bound is tight, but it remains open whether the second is, or whether only linear complexity is possible.

The expected extremes in a Delaunay triangulation.
M. Bern, D. Eppstein, and F. Yao.
18th Int. Coll. Automata, Languages and Programming, Madrid, Spain, 1991.
Springer, Lecture Notes in Comp. Sci. 510, 1991, 674–685, doi:10.1007/3-540-54233-7_173.
Int. J. Comp. Geom. & Appl. 1 (1): 79–92, 1991, doi:10.1142/S0218195991000074.

Discusses the expected behavior of Delaunay triangulations for points chosen uniformly at random (without edge effects). The main result is that within a region containing \(n\) points, the expected maximum degree is \(O(\log n / \log\log n)\).

On nearest-neighbor graphs.
D. Eppstein, M. S. Paterson, and F. F. Yao.
Disc. Comp. Geom. 17: 263–282, 1997, doi:10.1007/PL00009293.

Paterson and Yao presented a paper at ICALP showing among other things that any connected nearest neighbor forest with diameter D has O(D⁹) vertices. This paper is the journal version; my contribution consists of improving that bound to O(D⁵), which is tight.