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