Delaunay set

În teoria spațiilor metrice , -nets , -packings , -coverings , mulțimi uniform discrete , mulțimi relativ dense și mulțimi Delaunay (numite după matematicianul sovietic Boris Nikolayevich Delaunay ) sunt definiții strâns legate de mulțimi de puncte și raza de impacare și raza de acoperire [1] a acestor mulțimi determină cât de bine sunt distanțate punctele acestor mulțimi. Aceste multimi au aplicatii in teoria codificarii , algoritmi de aproximare si teoria cvasicristalelor .

Definiții

Dacă ( M , d ) este un spațiu metric și X este o submulțime a lui M , atunci raza de împachetare a unei mulțimi X este jumătate din infimul său de distanțe între puncte distincte ale lui X. Dacă raza de împachetare este r , atunci bile deschise cu raza r centrate în punctele X nu se intersectează și orice bilă deschisă centrată într-un punct din X cu raza 2 r nu conține alte puncte ale lui X . Raza de acoperire a unei mulțimi X este infimul numerelor r astfel încât orice punct din M se află la distanța r sau mai mică de cel puțin un punct din X. Adică este cea mai mică rază astfel încât unirea bilelor închise de această rază cu centrele din mulțimea X este egală cu spațiul M . Un set X este un -ambalaj dacă raza de împachetare este /2 (în mod echivalent, distanța minimă este ), un -acoperire este o mulțime X cu raza de acoperire , iar un -net este o mulțime care este atât un -ambalaj, cât și un - acoperire . O mulțime se numește uniform discretă dacă are o rază de împachetare diferită de zero și relativ densă dacă are o rază de acoperire finită. O mulțime Delaunay este o mulțime care este atât uniform discretă, cât și relativ densă. Atunci orice -net este o mulțime Delaunay, dar inversul nu este adevărat [2] [3] [4] .

Sisteme și cristale corecte

O mulțime Delaunay se numește sistem regulat dacă grupul său de simetrie G acționează tranzitiv asupra mulțimii X (adică X este orbita G a unui punct). O mulțime Delaunay se numește cristal dacă X este orbita G a unei mulțimi finite. Sistemul corect este un caz special important al unui cristal [1] .

  1. În avion, orice set Delaunay în care toate cartierele 4R sunt echivalente este un sistem obișnuit.
  2. Într-un spațiu de orice dimensiune, valoarea lui 4R este de neîmbunătățit
  3. În spațiul 3D, orice set Delaunay în care toate clusterele 10R sunt echivalente este un sistem obișnuit.
  4. Într-un spațiu de orice dimensiune, există o limită superioară pentru o astfel de rază încât identitatea clusterelor de o rază dată în mulțimea Delaunay garantează corectitudinea acesteia [5] .

Construirea de rețele epsilon

Ca o definiție cu cele mai multe restricții, -rețelele nu sunt mai ușor de construit decât -packings , -coverings și seturi Delaunay. Totuși, dacă punctele mulțimii M sunt o mulțime bine ordonată , inducția transfinită arată că este posibil să se construiască o -net N , incluzând în N fiecare punct pentru care infimumul distanțelor până la mulțimea punctelor precedente este în ordine. cel putin . Având în vedere un set finit de puncte într-un spațiu euclidian cu dimensiuni mărginite, fiecare punct poate fi verificat în timp constant prin maparea celulelor cu diametrul la o rețea și folosind un tabel hash pentru a verifica care celule învecinate conțin deja N puncte . Astfel, -rețeaua poate fi construită în timp liniar [6] [7] .

Pentru spații metrice finite sau compacte mai generale, algoritmul alternativ al lui Teófilo González , bazat pe selecția punctelor cele mai exterioare , poate fi folosit pentru a construi o rețea finită . Acest algoritm începe cu o rețea goală N și adaugă la N punctul cel mai îndepărtat de N de M , rupând arbitrar conexiunile și se oprește când toate punctele lui M sunt la distanță de N [8] . În spații cu dimensiune limitată de dublare , algoritmul Gonzalez poate fi implementat cu timp de rulare pentru seturi de puncte cu o dependență polinomială între distanța cea mai mare și cea mai mică, precum și un algoritm pentru rezolvarea aproximativă a problemei cu același timp de rulare și seturi arbitrare. a punctelor [9] .

Aplicații

Teoria codificării

Pentru un cod C (un subset de ), raza de acoperire a lui C este cea mai mică valoare a lui r , astfel încât orice element este conținut în cel puțin o bilă cu raza r centrată pe un cuvânt de cod din C . Raza de împachetare a lui C este cea mai mare valoare a lui s, astfel încât setul de bile cu raza s centrat pe C sunt disjunși pe perechi. Din dovada legaturii Hamming, se poate obține că pentru

.

Prin urmare, și dacă egalitatea este valabilă, atunci . Cazul de egalitate înseamnă că a fost atinsă limita Hamming.

În teoria codului de corecție , un spațiu metric care conține un cod de bloc C , constă din șiruri de lungime constantă, să spunem n , peste un alfabet de dimensiunea q (poate fi gândit ca vectori ) cu distanțe Hamming . Acest spațiu este notat ca . Raza de acoperire și raza de ambalare a acestui spațiu metric sunt legate de capacitatea codurilor de a corecta erorile.

Algoritmi de aproximare

Har-Peled și Rachel [10] descriu o paradigmă algoritmică pe care o numesc „rețea și tăiere” pentru dezvoltarea algoritmilor de aproximare pentru anumite tipuri de probleme de optimizare geometrică definite pe seturi de puncte din spațiile euclidiene . Acest tip de algoritm funcționează prin următorii pași:

  1. Alegem un punct aleatoriu p dintr-o mulțime de puncte, găsim cel mai apropiat vecin q și setăm egal cu distanța dintre p și q .
  2. Verificarea dacă (aproximativ) este mai mare sau mai mică decât valoarea optimă (folosind o tehnică determinată de specificul problemei de optimizare care se rezolvă)
    • Dacă valoarea este mai mare, eliminăm din datele de intrare punctele ale căror vecine cele mai apropiate sunt mai departe de
    • Dacă valoarea este mai mică, construim un -net N și eliminăm puncte din intrare care nu aparțin lui N .

În ambele cazuri, numărul așteptat de puncte rămase este redus cu un factor constant, astfel încât timpul de rulare este determinat de pasul de testare. După cum au arătat, o astfel de paradigmă poate fi folosită pentru a construi algoritmi de aproximare rapidă pentru găsirea centrului k , găsirea unei perechi de puncte cu o distanță medie și unele probleme conexe.

Un sistem ierarhic de rețele, numit arbore de rețea , poate fi utilizat în spații cu dimensiunea de dublare mărginită pentru a construi perechi de descompunere bine separate , întinderi geometrice și o soluție aproximativă a problemei vecinului cel mai apropiat [9] [11] .

Cristalografie

Pentru punctele din spațiul euclidian, o mulțime X este o mulțime Meyer , dacă este relativ densă și diferența sa Minkowski este uniform discretă. În mod echivalent, X este o mulțime Meyer dacă și X este o mulțime Delaunay. Mulțimile Meyer sunt numite după Yves Meyer , care le-a introdus (cu o definiție diferită, dar echivalentă bazată pe analiza armonică ) ca model matematic pentru cvasicristale . Acestea includ seturi de puncte de rețea , plăci Penrose și sume Minkowski ale acestor mulțimi finite [12] .

Celulele Voronoi ale mulțimilor simetrice Delaunay formează poliedre de umplere a spațiului, care sunt numite plesioedre [13] .

Vezi și

Note

  1. ↑ 1 2 Dolbilin, 2016 , p. 32.
  2. ↑ Clarkson, 2006 , p. 326–335.
  3. ↑ Unele surse folosesc numele „ -network” pentru structura la care se face referire în acest articol ca „ -coverage”. Vezi, de exemplu, Sutherland, 1975 , p. 110
  4. ↑ Însuși Delaunay a numit astfel de sisteme de seturi.
  5. ↑ Dolbilin, 2016 , p. 32-33.
  6. ↑ Har-Peled, 2004 , p. 545–565.
  7. ↑ Har-Peled, Raichel, 2013 , p. 605–614.
  8. ↑ Gonzalez, 1985 , p. 293–306.
  9. ↑ 1 2 Har-Peled, Mendel, 2006 , p. 1148–1184.
  10. ↑ Har-Peled, Raichel, 2013 .
  11. ↑ Krauthgamer, Lee, 2004 , p. 798–807.
  12. ↑ Moody, 1997 , p. 403–441.
  13. ↑ Grünbaum și Shephard 1980 , p. 951–973.

Literatură

Link -uri