Graf nejbližších sousedů

Graf nejbližšího souseda ( GBC ) pro množinu P sestávající z n objektů v metrickém prostoru (například pro množinu bodů v rovině s euklidovskou metrikou ) je orientovaný graf , jehož vrcholy jsou prvky množiny P , v která má nasměrovanou hranu od p do q , je-li q nejbližším sousedem p (tj. vzdálenost od p ke q není větší než od p k jakémukoli jinému objektu z P ) [1] .

V mnoha diskusích je směr hran ignorován a GBS je definován jako běžný (neorientovaný) graf . Nejbližší sousedský vztah však není symetrický , tzn. jestliže q je nejbližší soused p , pak p není nutně nejbližší soused q .

V některých diskuzích, aby byl výběr nejbližšího souseda jedinečný, je indexována množina P a když je vybrán nejbližší objekt, je vybrán objekt s nejvyšším indexem [2] .

Graf k - nejbližšího souseda ( k -GBN ) je graf, ve kterém jsou dva vrcholy p a q spojeny hranou, pokud vzdálenost mezi p a q patří mezi k nejmenších vzdáleností od p k ostatním objektům v P . GBS je speciální případ k -GBS, konkrétně jde o 1-GBS. k -GBS splňují podmínky rovinné věty o rozdělení - lze je rozdělit na dva podgrafy s maximem vrcholů odstraněním ) bodů [3] .

Dalším speciálním případem je ( n  − 1)-GBS. Tento graf se nazývá graf vzdáleného souseda (FDN).

V teoretických diskusích o algoritmech se často předpokládá jakási obecná pozice , totiž že pro každý objekt je nejbližší (k-nejbližší) soused jedinečný. Při implementaci algoritmů je třeba vzít v úvahu, že tato podmínka není vždy splněna.

GDS, jak pro body v rovině, tak pro body ve vícerozměrných prostorech, nachází uplatnění například v kompresi dat , pro plánování pohybu a umisťování objektů . Ve statistické analýze lze k rychlému nalezení hierarchických shluků použít algoritmus řetězce nejbližšího souseda založený na cestách v tomto grafu . Grafy nejbližšího souseda jsou také předmětem výpočetní geometrie .

Grafy nejbližšího souseda pro množiny bodů

Jednorozměrný případ

Pro množinu bodů v rovině je nejbližším sousedem bodu levý nebo pravý (nebo oba) soused, pokud jsou seřazeny podle přímky. GBS je tedy cesta nebo les několika cest a může být postaven v čase O ( n log n ) řazením . Tento odhad je asymptoticky optimální pro některé výpočetní modely , protože zkonstruovaný GBS dává odpověď na problém jednoznačnosti prvku — stačí zkontrolovat, zda výsledný GBS obsahuje hranu nulové délky.

Vyšší rozměry

Pokud není výslovně uvedeno, předpokládá se, že grafy nejbližších sousedů jsou orientované grafy s jednoznačně definovanými sousedy, jak je popsáno v úvodu.

  1. Podél jakékoli orientované cesty v GBS se délky hran nezvětšují [2] .
  2. Možné jsou pouze cykly délky 2 v GBS a každá slabě propojená komponenta GDS se 2 a více vrcholy má právě jeden 2-cyklus [2] .
  3. Pro rovinné body je GBS rovinný graf s vrcholovými stupni nepřesahujícími 6. Pokud jsou body v obecné poloze , vrcholový stupeň nepřesahuje 5 [2] .
  4. GBS (považovaný za neorientovaný graf s rozlišením několika nejbližších sousedů) množiny bodů v rovině nebo jakémkoli prostoru vyšší dimenze je podgrafem Delaunayovy triangulace , Gabrielova grafu a semi- Y grafu [ 4] . Jsou-li body ve společné pozici nebo je-li nastavena podmínka jedinečného nejbližšího souseda, GBS je les , podgraf euklidovského minimálního kostry .

Poznámky

  1. ↑ Preparata, Sheimos, 1989 .
  2. ↑ 1 2 3 4 Eppstein, Paterson, Yao, 1997 , str. 263–282.
  3. ↑ Miller, Teng, Thurston, Vavasis, 1997 .
  4. ↑ Rahmati, King, Whitesides, 2013 , str. 137–144.

Literatura

Odkazy