**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 15

*n*/2. The complexity of cells cut by a convex*k*-gon is O(*n*α(*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.

*Int. J. Comp. Geom. & Appl.*1 (1): 79–92, 1991.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 bounded to within a constant factor of log*n*/ log log*n.*(BibTeX – Citations – CiteSeer – ACM DL – ACM DL (2))

**On nearest-neighbor graphs**.

D. Eppstein, M. S. Paterson, and F. F. Yao.

*Disc. Comp. Geom.*17: 263–282, 1997.Paterson and Yao presented a paper at ICALP showing among other things that any connected nearest neighbor forest with diameter

*D*has O(*D*^{9}) vertices. This paper is the journal version; my contribution consists of improving that bound to O(*D*^{5}), which is tight.(BibTeX – CiteSeer – Citations)

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

Semi-automatically filtered from a common source file.