Kaavio lähimmistä naapureista

Lähin naapurigraafi ( GBC ) joukolle P , joka koostuu n :stä metriavaruudessa olevasta objektista (esimerkiksi pistejoukolle tasossa , jossa on euklidinen metriikka ) on suunnattu graafi , jonka kärjet ovat joukon P elementtejä . jolla on suunnattu reuna p :stä q :hen , jos q on p : n lähin naapuri (eli etäisyys p :stä q :hen ei ole suurempi kuin p :stä mihinkään muuhun P :n kohteeseen ) [1] .

Monissa keskusteluissa reunojen suunta jätetään huomiotta ja GBS määritellään tavalliseksi (suuntaamattomaksi) graafiksi . Lähin naapurisuhde ei kuitenkaan ole symmetrinen , ts. jos q on p :n lähin naapuri , niin p ei välttämättä ole q :n lähin naapuri .

Joissakin keskusteluissa lähimmän naapurin valinnan tekemiseksi ainutlaatuiseksi joukko P indeksoidaan ja kun lähin kohde valitaan, valitaan kohde, jolla on korkein indeksi [2] .

K - lähin naapurigraafi ( k -GBN ) on graafi, jossa kaksi kärkeä p ja q on yhdistetty reunalla, jos p:n ja q:n välinen etäisyys on k pienimmän etäisyyden p : stä muihin P :n objekteihin joukossa . GBS on k -GBS:n erikoistapaus, nimittäin se on 1-GBS. k -GBS täyttävät tasomaisen osiointilauseen ehdot - ne voidaan jakaa kahteen aligraafiin, joissa on maksimipisteitä poistamalla ) -pisteitä [3] .

Toinen erikoistapaus on ( n  − 1)-GBS. Tätä kuvaajaa kutsutaan kaukonaapurigraafiksi (FDN).

Algoritmien teoreettisessa keskustelussa oletetaan usein jonkinlaista yleistä asemaa , nimittäin että jokaiselle objektille lähin (k-lähin) naapuri on yksilöllinen. Algoritmeja toteutettaessa on otettava huomioon, että tämä ehto ei aina täyty.

GDS, sekä tason pisteille että pisteille moniulotteisissa tiloissa, löytää sovelluksia esimerkiksi tiedon pakkaamiseen , liikkeen suunnitteluun ja objektien sijoittamiseen . Tilastoanalyysissä lähimmän naapuriketjun algoritmia , joka perustuu tämän kaavion polkuihin , voidaan käyttää hierarkkisten klustereiden nopeaan löytämiseen . Lähin naapurikuvaajat ovat myös laskennallisen geometrian aihe .

Lähin naapurikuvaajat pistejoukoille

Yksiulotteinen kotelo

Tason pistejoukolle pisteen lähin naapuri on vasen tai oikea (tai molemmat) naapuri, jos ne on lajiteltu suoraa viivaa pitkin. GBS on siis usean polun polku tai metsä , ja se voidaan rakentaa O ( n log n ) ajassa lajittelemalla . Tämä arvio on asymptoottisesti optimaalinen joillekin laskennallisille malleille , koska rakennettu GBS antaa vastauksen elementin ainutlaatuisuusongelmaan — riittää, kun tarkistetaan, sisältääkö tuloksena saatu GBS nollapituisen reunan.

Suuremmat mitat

Ellei nimenomaisesti mainita, lähimpien naapurigraafien oletetaan olevan suunnattuja kaavioita, joissa on yksilöllisesti määritellyt naapurit, kuten johdannossa on kuvattu.

  1. Millä tahansa suunnatulla reitillä GBS:ssä reunojen pituudet eivät kasva [2] .
  2. Vain 2 pituiset syklit GBS:ssä ovat mahdollisia, ja jokaisella heikosti kytketyllä GDS-komponentilla, jossa on 2 tai useampia huippuja, on täsmälleen yksi 2-sykli [2] .
  3. Tasopisteille GBS on tasograafi , jonka kärkiasteet eivät ylitä 6:ta. Jos pisteet ovat yleisasennossa , huippupisteen aste ei ylitä 5 [2] .
  4. Tason tai minkä tahansa korkeamman tilan pistejoukon GBS (jota pidetään suuntaamattomana graafina, jolla on useita lähimmän naapurin resoluutiota) on Delaunayn kolmiomittauksen , Gabriel-graafin ja puoli- Y-graafin aligraafi [ 4] . Jos pisteet ovat yhteisessä asennossa tai jos yksilöllinen lähin naapuri on asetettu, GBS on metsä , euklidisen minimivirittävän puun aligraafi .

Muistiinpanot

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

Kirjallisuus

Linkit