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

The diameter of nearest neighbor graphs

  • Author(s): Eppstein, David
  • et al.
Abstract

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

Main Content
Current View