Skip to main content
eScholarship
Open Access Publications from the University of California
Refine Search

Donald Bren School of Information and Computer Sciences

ICS Technical Reports bannerUC Irvine

The diameter of nearest neighbor graphs

Abstract

Any connected plane nearest neighbor graph has diameter Ω(n^1/6). This bound generalizes to Ω(n^1/3d) in any dimension d.


Top