Graf över närmaste grannar

En närmaste grannegraf ( GBC ) för en mängd P som består av n objekt i ett metriskt utrymme (till exempel för en uppsättning punkter på ett plan med en euklidisk metrik ) är en riktad graf vars hörn är element i mängden P , i som det finns en riktad kant från p till q , om q är närmaste granne till p (dvs avståndet från p till q är inte större än från p till något annat objekt i P )[1] .

I många diskussioner ignoreras kanternas riktning och GBS definieras som en vanlig (oriktad) graf . Den närmaste grannrelationen är dock inte symmetrisk , dvs. om q är p :s närmaste granne , så är p inte nödvändigtvis q :s närmaste granne .

I vissa diskussioner, för att göra det närmaste grannvalet unikt, indexeras mängden P och när det närmaste objektet väljs väljs objektet med det högsta indexet [2] .

En k -närmaste granngraf ( k - GBN ) är en graf där två hörn p och q är sammankopplade med en kant om avståndet mellan p och q är bland de k minsta avstånden från p till andra objekt i P . GBS är ett specialfall av k -GBS, det är nämligen 1-GBS. k -GBS uppfyller villkoren för planar partitioneringssatsen - de kan delas in i två subgrafer med maximalt vertex genom att ta bort ) punkter [3] .

Ett annat specialfall är ( n  − 1)-GBS. Denna graf kallas för bortre granngrafen (FDN).

I teoretiska diskussioner om algoritmer antas ofta någon sorts generell position , nämligen att för varje objekt är den närmaste (k-närmaste) granne unik. Vid implementering av algoritmer måste man ta hänsyn till att detta villkor inte alltid är uppfyllt.

GDS, både för punkter på planet och för punkter i flerdimensionella utrymmen, hittar tillämpningar, till exempel vid datakomprimering , för rörelseplanering och objektplacering . I statistisk analys kan den närmaste grannkedjans algoritm baserad på vägarna i denna graf användas för att snabbt hitta hierarkiska klustringar . Närmaste granngrafer är också ett ämne för beräkningsgeometri .

Närmaste granne grafer för uppsättningar av punkter

Endimensionellt fall

För en uppsättning punkter i ett plan är den närmaste granne till en punkt den vänstra eller högra (eller båda) granne om de är sorterade längs en rät linje. Således är en GBS en bana eller en skog av flera stigar och kan byggas på O ( n log n ) tid genom att sortera . Denna uppskattning är asymptotiskt optimal för vissa beräkningsmodeller , eftersom den konstruerade GBS ger svaret på elementets unikhetsproblem — det räcker att kontrollera om den resulterande GBS innehåller en kant med noll längd.

Högre dimensioner

Om inte uttryckligen anges antas graferna för närmaste grannar vara riktade grafer med unikt definierade grannar, som beskrivs i inledningen.

  1. Längs någon orienterad bana i GBS ökar inte kanternas längder [2] .
  2. Endast cykler med längd 2 i GBS är möjliga, och varje svagt ansluten GDS-komponent med 2 eller fler hörn har exakt en 2-cykel [2] .
  3. För plana punkter är GBS en plan graf med vertexgrader som inte överstiger 6. Om punkterna är i allmän position överstiger inte vertexgraden 5 [2] .
  4. GBS (betraktad som en oriktad graf med flera närmaste grannupplösning) för en uppsättning punkter i ett plan eller något utrymme med högre dimension är en subgraf av en Delaunay-triangulering , en Gabriel-graf och en semi- Y-graf [ 4] . Om punkterna är i en gemensam position, eller om det unika villkoret för närmaste granne är påtvingat, är GBS en skog , en subgraf av det euklidiska minimumspännande trädet .

Anteckningar

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

Litteratur

Länkar