Graf nejbližšího souseda

Graf nejbližšího souseda (nearest neighbor graph – NNG) pro n objektů v množině P v metrickém prostoru (např. pro množiny bodů v rovině euklidovské vzdálenosti) je orientovaný graf, kde uzly jsou spojovány hranami směřujícími od p do q, pokud q je nejbližší soused p (tj. vzdálenost od p do q je větší než od p na jiný objekt z množiny P).

Graf nejbližšího souseda pro 100 bodů v Euklidovské rovině.

V mnoha diskuzích jsou směry hran ignorovány a NNG je definován jako neorientovaný graf. Nicméně nejbližší sousední vztah není symetrický, tzn. p není nutně nejbližším sousedem q.

Graf k-nejbližších sousedů (k-nearest neighbor graph - k-NNG) je metoda, ve které jsou dva uzly p a q spojeny hranou, je-li vzdálenost p a q mezi K-tou nejmenší vzdáleností od p k ostatním objektům z množiny P. NNG je zvláštní případ k-NNG, konkrétně se jedná o 1-NNG.

Dalším speciálním případem je (n -1)-NNG. Tato metoda se nazývá graf nejzvdálenějšího souseda (farthest neighbor graph - FNG).

V teoretické diskuzi ohledně druhu v obecné poloze se často předpokládá, že zejména graf nejbližšího souseda je jedinečný pro každou množinu bodů. V implementaci těchto algoritmů je třeba mít na paměti, že to není vždy správný případ.

Graf nejbližšího souseda v rovině i ve vícerozměrných prostorech najde uplatnění např. v kompresi dat, plánování pohybu a lokální analýze. Ve statistické analýze, shlukové analýze a na základě následujících cest v tomto grafu je možné použít pro rychlé hierarchické získávání dat. Graf nejbližšího souseda je také předmětem výpočetní geometrie.

Reference

V tomto článku byl použit překlad textu z článku Nearest neighbor graph na anglické Wikipedii.