title: Nearest neighbor graph
text: De nearest neighbor graph (NNG) van een verzameling punten in de Euclidische ruimte is de gerichte graaf waarin vanuit elk punt  een kant vertrekt naar zijn meest nabije buur .
  
  De meest nabije buur (nearest neighbor)  van een punt  is het punt , met , waarvoor de afstand  minimaal is. 
  
  Het is mogelijk dat er meerdere punten op dezelfde minimale afstand van  liggen; in dat geval kiest men als de meest nabije buur het punt met de hoogste index.
  
  De relatie " is de naaste buur van " is niet symmetrisch, vandaar dat de NNG een gerichte graaf is.
  
  Eigenschappen
  
   Voor een verzameling punten in het euclidische vlak is de NNG een planaire graaf. De hoek tussen twee kanten die in een punt toekomen is ten minste 60°. Er kunnen dus hoogstens zes kanten in een punt toekomen; anders gezegd: de graad van een punt is hoogstens zes.
   Langs elk gericht pad in een NNG hebben de opeenvolgende kanten een niet-stijgende lengte.
   De enige cykels in de NNG zijn 2-cykels (punt  is de NN van punt  en vice versa).
   Als de NNG wordt herleid tot een niet-gerichte graaf (waarbij de 2-cykels vervangen worden door één kant tussen de twee punten) is de NNG een subgraaf van de Delaunay-triangulatie van de verzameling punten en van de minimaal opspannende boom.
   In het algemeen is de NNG een niet-samenhangende graaf, een "woud" van deelgrafen van de minimaal opspannende boom die "puntenclusters" verbinden. Voor een verzameling van  uniform verdeelde, willekeurig gekozen punten in het eenheidsvierkant is het aantal deelgrafen van de NNG asymptotisch gelijk aan ongeveer .
  
  Uitbreiding
  De -nearest neighbor graph (k-NNG) is een gerichte graaf waarin elk punt  verbonden is met de  meest nabije buren.  kan gaan van 1 tot  (als  het totaal aantal punten in de verzameling is). De NNG is een speciaal geval van de -NNG, namelijk voor .
  
  Toepassingen
  Het bepalen van de NNG of -NNG vindt toepassing in onder meer de computationele meetkunde, computergraphics, patroonherkenning en geografische informatiesystemen.
  
  Meetkunde
  Grafentheorie