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

The diameter of nearest neighbor graphs

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

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

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View