David Eppstein - Publications

Publications with Mike Paterson

• 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⁹) vertices. This paper is the journal version; my contribution consists of improving that bound to O(D⁵), which is tight.