Legközelebbi szomszéd-gráf

A matematika, azon belül a gráfelmélet területén n darab valamely metrikus térbeli P objektumhoz (pl. pontok halmazához a síkban euklideszi távolsággal) tartozó legközelebbi szomszéd-gráf (nearest neighbor graph, NNG) olyan irányított gráf, melynek csúcshalmazában P minden eleméhez egy-egy csúcs tartozik, és p-ből q csúcsba pontosan akkor mutat irányított él, ha q a p legközelebbi szomszédja (azaz a p és q távolsága nem nagyobb, mint p és a P-beli bármely más objektum távolsága).^[1]

Sok esetben az élek irányítottságától eltekintenek, és az NNG-t irányítatlan gráfként definiálják. A legközelebbi szomszéd-reláció azonban nem szimmetrikus, tehát definícióban szereplő p nem feltétlenül q legközelebbi szomszédja.

Ha egy cikkben szükséges, hogy az objektumok legközelebbi szomszédja egyértelmű legyen, a P halmaz elemeit megszámozzák és döntetlen esetén pl. a legmagasabb indexű elemet tekintik a legközelebbi szomszédnak.^[2]

A k-legközelebbi szomszéd-gráf (k-NNG) olyan gráf, melyben p-ből q-ba akkor húzódik él, ha a p és q közötti távolság a p és a többi P-beli objektum közötti távolságok között a k-adik legkisebb távolságok között van. Az NNG a k-NNG speciális esete, méghozzá ez az 1-NNG. A k-NNG-kre egyfajta szeparációs tétel vonatkozik: O(k^1/dn^1 − 1/d) csúcs eltávolításával két, egyenként legfeljebb n(d + 1)/(d + 2) csúcsból álló részgráffá particionálhatók.^[3]

Egy másik speciális eset az (n − 1)-NNG. Ez a gráf a legtávolabbi szomszéd-gráf (farthest neighbor graph, FNG).

Az algoritmusok elméleti tárgyalása során az egyszerűség kedvéért gyakran az objektumok általános helyzetét feltételezik, tehát hogy a legközelebbi (k-legközelebbi) szomszéd minden objektum esetében egyedi. Az algoritmusok implementációjánál fontos odafigyelni arra, hogy az egyediség nem minden esetben áll fenn.

A síkban, vagy akár sokdimenziós terekben elhelyezkedő pontok legközelebbi szomszéd-gráfjait több helyen alkalmazzák: adattömörítésben, mozgástervezésben és a létesítmény-elhelyezési probléma megoldásában egyaránt. A statisztikai analízis legközelebbi szomszéd-láncalgoritmusa az NNG-beli utak követésével talál meg hierarchikus klasztereket nagy sebességgel. Az NNG-k a számítási geometria vizsgálati területébe is tartoznak.

Ponthalmazok NNG-i

Egydimenziós eset

Az egy egyenesen elhelyezkedő ponthalmaz esetén egy pont legközelebbi szomszédja a tőle balra és/vagy jobbra elhelyezkedő pont. Ebből adódóan az NNG vagy egy útgráf, vagy diszjunkt útgráfokból álló erdő, és rendezés segítségével O(n log n) idő alatt előállítható. Ez a becslés egyes számítási modellekben aszimptotikusan optimális, mivel a megszerkesztett NNG megadja a választ a listaelem-egyediség problémára: elegendő annak vizsgálata, hogy az NNG tartalmaz-e nulla hosszúságú élt.

Magasabb dimenziók

A továbbiakban feltételezzük, hogy az NNG-k irányított gráfok, és a legközelebbi szomszédok egyértelműen meghatározhatók. A következőket állíthatjuk:

Egy NNG bármely irányított útjának élhosszai monoton csökkenőek.^[2]
Egy NNG-ben csak 2 hosszúságú körök lehetségesek és minden, legalább két csúcsból álló gyengén összefüggő komponensben pontosan egy 2-kör található.^[2]
Síkbeli pontok NNG-je síkbarajzolható gráf, mely csúcsainak fokszáma legfeljebb 6 lehet. Általános helyzetű pontok esetén a maximális fokszám csak 5.^[2]
Egy sík vagy magasabb dimenziójú tér pontjainak NNG-je (itt irányítatlan gráfként kezelve és a többszörös legközelebbi szomszédokat is megengedve) a pontok Delaunay-háromszögelésének, Gabriel-gráfjának és a fél-Yao-gráfjának is részgráfja.^[4] Ha a pontok általános helyzetűek vagy ha a szomszédok egyediségét is megköveteljük, az NNG egy erdő, az euklideszi minimális feszítőfa részgráfja.

Fordítás

Ez a szócikk részben vagy egészben a Nearest neighbor graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

↑ Franco P. Preparata and Michael Ian Shamos. Computational Geometry - An Introduction. Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6 (1985)
↑ ^a ^b ^c ^d (1997) „On nearest-neighbor graphs”. Discrete and Computational Geometry 17 (3), 263–282. o. DOI:10.1007/PL00009293.
↑ (1997) „Separators for sphere-packings and nearest neighbor graphs”. J. ACM 44 (1), 1–29. o. DOI:10.1145/256292.256294.
↑ (2013) „Kinetic data structures for all nearest neighbors and closest pair in the plane”. Proceedings of the 29th ACM Symposium on Computational Geometry: 137–144. doi:10.1145/2462356.2462378.

További információk

C++ library for efficient nearest-neighbor graph construction Archiválva 2021. január 23-i dátummal a Wayback Machine-ben

[1] Franco P. Preparata and Michael Ian Shamos. Computational Geometry - An Introduction. Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6 (1985)

[epy-2] (1997) „On nearest-neighbor graphs”. Discrete and Computational Geometry 17 (3), 263–282. o. DOI:10.1007/PL00009293.

[3] (1997) „Separators for sphere-packings and nearest neighbor graphs”. J. ACM 44 (1), 1–29. o. DOI:10.1145/256292.256294.

[Rahmati-4] (2013) „Kinetic data structures for all nearest neighbors and closest pair in the plane”. Proceedings of the 29th ACM Symposium on Computational Geometry: 137–144. doi:10.1145/2462356.2462378.

[1]

[2]

[3]

[4]