Delaunay setti

Metristen tilojen teoriassa -verkot , -pakkaukset , -päällysteet , tasaisesti erilliset joukot , suhteellisen tiheät joukot ja Delaunay-joukot (nimetty Neuvostoliiton matemaatikon Boris Nikolajevitš Delaunayn mukaan) ovat läheisesti liittyviä määritelmiä pistejoukoille ja pakkaussäteelle ja näiden joukkojen peittosäde [1] määrittää, kuinka hyvin näiden joukkojen pisteet ovat erillään. Näillä joukoilla on sovelluksia koodausteoriassa , approksimaatioalgoritmeissa ja kvasikideteoriassa .

Määritelmät

Jos ( M , d ) on metrinen avaruus ja X on M :n osajoukko , niin joukon X pakkaussäde on puolet sen X :n erillisten pisteiden välisistä etäisyyksistä . Jos pakkaussäde on r , niin pisteissä X olevat avoimet pallot, joiden säde on r , eivät leikkaa toisiaan, ja mikään avoin pallo, joka on keskitetty pisteeseen X , jonka säde on 2 r , ei sisällä muita X :n pisteitä . Joukon X peittosäde on lukujen r infimumi siten, että mikä tahansa piste M :ssä on etäisyydellä r tai vähemmän vähintään yhdestä X :n pisteestä . Toisin sanoen se on pienin säde, jolla tämän säteen suljettujen pallojen ja joukon X keskipisteiden liitto on yhtä suuri kuin avaruus M . Joukko X on -pakkaus , jos pakkaussäde on /2 (vastaavasti pienin etäisyys on ), -cover on joukko X peittosäteellä ja -net on joukko, joka on sekä -pakkaus että - kansi . Joukkoa kutsutaan tasaisesti diskreetiksi , jos sillä on nollasta poikkeava pakkaussäde, ja suhteellisen tiheäksi , jos sillä on rajallinen peittosäde. Delaunay -sarja on joukko, joka on sekä tasaisesti diskreetti että suhteellisen tiheä. Silloin mikä tahansa -verkko on Delaunayn joukko, mutta päinvastoin ei pidä paikkaansa [2] [3] [4] .

Oikeat järjestelmät ja kiteet

Delaunayn joukkoa kutsutaan säännölliseksi järjestelmäksi, jos sen symmetriaryhmä G toimii transitiivisesti joukossa X (eli X on yhden pisteen G -kiertorata). Delaunayn joukkoa kutsutaan kiteeksi , jos X on jonkin äärellisen joukon G -kiertorata. Oikea järjestelmä on tärkeä kiteen erikoistapaus [1] .

  1. Lentokoneessa mikä tahansa Delaunay-sarja, jossa kaikki 4R-alueet ovat vastaavia, on tavallinen järjestelmä.
  2. Minkä tahansa ulottuvuuden avaruudessa 4R:n arvoa ei voida parantaa
  3. 3D-avaruudessa mikä tahansa Delaunay-joukko, jossa kaikki 10R-klusterit ovat vastaavia, on tavallinen järjestelmä.
  4. Minkä tahansa ulottuvuuden avaruudessa on yläraja sellaiselle säteelle, että tietyn säteen klusterien identiteetti Delaunay-joukossa takaa sen oikeellisuuden [5] .

Epsilon-verkkojen rakentaminen

Eniten rajoituksia sisältävänä määritelmänä -verkkoja ei ole helpompi rakentaa kuin -pakkaukset, -coverings ja Delaunay-joukot. Kuitenkin, jos joukon M pisteet ovat hyvin järjestetyt joukot , äärellinen induktio osoittaa, että on mahdollista rakentaa -net N , mukaan lukien N :ssä jokainen piste, jolle etäisyyden infimumi edeltävien pisteiden joukkoon on kunnossa ainakin . Kun otetaan huomioon rajallinen joukko pisteitä rajatussa euklidisessa avaruudessa, jokainen piste voidaan tarkistaa vakioajassa kartoittamalla halkaisijasolut hilaan ja käyttämällä hash-taulukkoa tarkistamaan, mitkä naapurisolut sisältävät jo N pistettä . Siten -verkko voidaan rakentaa lineaarisessa ajassa [6] [7] .

Yleisemmille äärellisille tai kompakteille metriavaruksille voidaan käyttää Teófilo Gonzálezin vaihtoehtoista algoritmia , joka perustuu uloimpien pisteiden valintaan , rakentamaan äärellinen verkko. Tämä algoritmi alkaa tyhjästä verkosta N ja lisää N :ään pisteen , joka on kauimpana N :stä M :stä , katkaisemalla mielivaltaisesti yhteyksiä, ja pysähtyy, kun M :n kaikki pisteet ovat etäisyyden päässä N :stä [8] . Tiloissa, joilla on rajoitettu kaksinkertaistuminen , Gonzalez-algoritmi voidaan toteuttaa ajoajalla pisteiden sarjoille, joilla on polynomiriippuvuus suurimman ja pienimmän etäisyyden välillä, sekä algoritmilla ongelman likimääräiseen ratkaisuun samalla ajoajalla ja mielivaltaisilla sarjoilla. kohdista [9] .

Sovellukset

Koodausteoria

Koodille C (osajoukko ), C : n peittosäde on pienin r :n arvo siten, että mikä tahansa elementti sisältyy vähintään yhteen sädepalloon r , joka on keskitetty C :n koodisanaan . C :n tiivistyssäde on s :n suurin arvo siten, että C :hen keskitetyt pallot, joiden säde on s , ovat pareittain hajallaan. Hamming-sidotun todistuksen perusteella voidaan saada se

.

Siksi, ja jos tasa-arvo pätee, niin . Tasa-arvon tapaus tarkoittaa, että Hammingin raja on saavutettu.

Korjauskooditeoriassa metriavaruus , joka sisältää lohkokoodin C , koostuu vakiopituisista merkkijonoista, esimerkiksi n , aakkoston, jonka koko on q (voidaan ajatella vektoreina ) yli, ja Hamming-etäisyydet . Tämä tila on merkitty . Tämän metrialueen peitto- ja pakkaussäde liittyvät koodien kykyyn korjata virheitä.

Approksimaatioalgoritmit

Har-Peled ja Rachel [10] kuvaavat algoritmista paradigmaa, jota he kutsuvat "verkostoitumiseksi ja karsimiseksi" approksimaatioalgoritmien kehittämiseksi tietyntyyppisille geometrisille optimointiongelmille, jotka on määritelty pistejoukoissa euklidisissa avaruudessa . Tämän tyyppinen algoritmi toimii seuraavasti:

  1. Valitsemme pistejoukosta satunnaisen pisteen p , etsimme lähimmän naapurin q ja asetamme p :n ja q :n välisen etäisyyden .
  2. Tarkistaa, onko (likimäärin) suurempi vai pienempi kuin optimaalinen arvo (käyttäen ratkattavan optimointiongelman erityispiirteiden määräämää tekniikkaa)
    • Jos arvo on suurempi, syöttötiedoista poistetaan pisteet, joiden lähimmät naapurit ovat kauempana kuin
    • Jos arvo on pienempi, rakennamme -net N ja poistamme syötteestä kohdat, jotka eivät kuulu N :ään .

Molemmissa tapauksissa odotettua jäljellä olevien pisteiden määrää pienennetään vakiokertoimella, joten käyntiaika määräytyy testivaiheen mukaan. Kuten he osoittivat, tällaista paradigmaa voidaan käyttää nopeiden approksimaatioalgoritmien rakentamiseen k-keskuksen löytämiseksi, keskimääräisen etäisyyden pisteparin löytämiseksi ja joitain asiaan liittyviä ongelmia.

Hierarkkista verkkojärjestelmää, jota kutsutaan verkkopuuksi , voidaan käyttää rajatun kaksinkertaistuvan ulottuvuuden avaruudessa rakentamaan hyvin erotettuja hajoamispareja , geometrisia ulottuvuuksia ja likimääräistä ratkaisua lähimmän naapurin ongelmaan [9] [11] .

Kristallografia

Euklidisen avaruuden pisteille joukko X on Meyerin joukko , jos se on suhteellisen tiheä ja sen Minkowski-ero on tasaisen diskreetti. Vastaavasti X on Meyerin joukko ja X on Delaunayn joukko. Meyer-joukot on nimetty Yves Meyerin mukaan, joka esitteli ne (erilainen mutta vastaava harmoninen analyysiin perustuva määritelmä ) kvasikiteiden matemaattisena mallina . Ne sisältävät hilapisteiden joukot , Penrose -laatoitukset ja näiden äärellisten joukkojen Minkowskin summat [12] .

Symmetristen Delaunay-joukkojen Voronoi-solut muodostavat tilaa täyttäviä monitahoja, joita kutsutaan plesioedreiksi [13] .

Katso myös

Muistiinpanot

  1. ↑ 1 2 Dolbilin, 2016 , s. 32.
  2. ↑ Clarkson, 2006 , s. 326-335.
  3. ↑ Jotkut lähteet käyttävät nimeä " -verkko" rakenteelle, johon tässä artikkelissa viitataan nimellä " -coverage". Katso esimerkiksi Sutherland, 1975 , s. 110
  4. ↑ Delaunay itse kutsui tällaisia ​​joukkojärjestelmiä .
  5. ↑ Dolbilin, 2016 , s. 32-33.
  6. ↑ Har-Peled, 2004 , s. 545–565.
  7. ↑ Har-Peled, Raichel, 2013 , s. 605–614.
  8. ↑ Gonzalez, 1985 , s. 293–306.
  9. ↑ 1 2 Har-Peled, Mendel, 2006 , s. 1148–1184.
  10. ↑ Har-Peled, Raichel, 2013 .
  11. ↑ Krauthgamer, Lee, 2004 , s. 798–807.
  12. ↑ Moody, 1997 , s. 403–441.
  13. ↑ Grünbaum ja Shephard 1980 , s. 951–973.

Kirjallisuus

Linkit