У теорії метричних просторів, -мережі, -пакування, -покриття, рівномірно дискретні множини, відносно щільні множини і множини Делоне (названі ім'ям радянського математика Бориса Миколайовича Делоне) є тісно пов'язаними визначеннями множин точок, а радіус пакування і радіус покриття цих множин визначають, наскільки добре точки цих множин рознесені. Ці множини застосовують у теорії кодування, апроксимаційних алгоритмах і теорії квазікристалів.
Визначення
Якщо (M,d) — метричний простір, а X — підмножина M, то радіус пакування множини X — це половина його інфімуму відстаней між різними точками X. Якщо радіус пакування дорівнює r, то відкриті кулі радіуса r з центрами в точках X не перетинаються, а будь-яка відкрита куля з центром у точці з X і радіусом 2r не містить інших точок X. Радіус покриття множини X — це інфімум чисел r, таких що будь-яка точка M лежить не далі ніж на відстані r принаймні від однієї точки X. Тобто це найменший радіус, такий, що об'єднання замкнутих куль цього радіусу з центрами у множині X дорівнює простору M. Множина X — це -пакування, якщо радіус пакування /2 (еквівалентно, найменша відстань ), -покриття — це множина X із радіусом покриття , а -мережа — це множина, що є одночасно і -пакуванням, і -покриттям. Множину називають однорідно дискретною, якщо воно має ненульовий радіус пакування і відносно щільною, якщо має скінченний радіус покриття. Множина Делоне — це множина, що є одночасно однорідно дискретною, і відносно щільною. Тоді будь-яка -мережа є множиною Делоне, але протилежне хибне.
Правильні системи та кристали
Множину Делоне називають правильною системою, якщо її група симетрій G діє транзитивно на множині X (тобто X є G-орбітою однієї точки). Множину Делоне називають кристалом, якщо X є G-орбітою деякої скінченної множини. Правильна система є важливим окремим випадком кристала.
- На площині будь-яка множина Делоне, в якій усі 4R-околи еквівалентні, є правильною системою.
- У просторі будь-якої розмірності значення 4R не покращується.
- У тривимірному просторі будь-яка множина Делоне, в якій усі 10R-кластери еквівалентні, є правильною системою.
- У просторі будь-якої розмірності є верхня оцінка для такого радіуса, що ідентичність кластерів даного радіуса у множині Делоне гарантує її правильність.
Побудова епсилон-мереж
Через визначення з найбільшими обмеженнями, -мережі побудувати не простіше ніж -пакування, -покриття та множини Делоне. Однак, якщо точки множини M утворюють цілком упорядковану множину, трансфінітна індукція показує, що можна побудувати -мережу N, включаючи N кожну точку, на яку інфімум відстаней до множини попередніх точок у порядку дорівнює принаймні . Для скінченної множини точок у евклідовому просторі обмеженої розмірності кожну точку можна перевірити за сталий час відображенням у ґратку комірок діаметра та використанням геш-таблиці для перевірки, які сусідні комірки вже містять точки N. Таким чином, -мережу можна побудувати за лінійний час.
У загальніших скінченних або компактних метричних просторах для побудови скінченної -мережі можна використати альтернативний алгоритм [en], заснований на [en]. Цей алгоритм починає з порожньої мережі N і додає в N найвіддаленішу від N точку з M, довільно розриваючи зв'язки, і зупиняється, коли всі точки M лежать на відстані від N. У просторах обмеженої розмірності подвоєння алгоритм Гонсалеса для множин точок з поліноміальною залежністю між найбільшою і найменшою відстанню можна реалізувати з часом роботи , а також реалізувати алгоритм наближеного розв'язання задачі з тим самим часом роботи та довільними множинами точок.
Застосування
Теорія кодування
У теорії кодів з виправленням помилок метричний простір, що містить блоковий код C, складається з рядків фіксованої довжини, скажімо, n, взятих за алфавітом розміру q (можна розглядати як вектори) з метрикою Геммінга. Цей простір позначають . Радіус покриття та радіус пакування цього метричного простору пов'язані з можливістю кодів коригувати помилки.
Для коду C (підмножина ), радіус покриття C — це найменше значення r, таке, що будь-який елемент міститься принаймні в одній кулі радіуса r з центром у кодовому слові з C. Радіус пакування C — це найбільше значення s, таке, що множина куль радіуса s із центрами в C попарно не перетинаються. З доведення межі Геммінга можна отримати, що для має місце
- .
Тому, і, якщо має місце рівність, то . Випадок рівності означає, що досягнуто межі Геммінга.
Алгоритми наближення
[en] і Рейчел описують алгоритмічну парадигму, яку вони називають «побудова мережі та обрізання» для розробки апроксимаційних алгоритмів для геометричних задач оптимізації певних типів, визначених на множині точок в евклідових просторах. Алгоритм цього типу включає такі кроки:
- Вибираємо випадкову точку p зі множини точок, знаходимо найближчого сусіда q і вважаємо рівним відстані між p і q.
- Перевіряємо, чи (приблизно) більше, чи менше від оптимального значення (використовуючи техніку, що визначається специфікою розв'язуваної задачі оптимізації)
- Якщо значення більше, видаляємо зі вхідних даних точки, найближчі сусіди яких розташовані далі, ніж на
- Якщо значення менше, будуємо -мережу N і видаляємо зі вхідних даних точки, що не належать N.
В обох випадках очікуване число точок, що залишилися, зменшується на сталий множник, так що час роботи визначається кроком тестування. Як вони показали, таку парадигму можна використати для побудови швидких апроксимаційних алгоритмів пошуку [en], пошуку пари точок зі середньою відстанню та деяких пов'язаних задач.
Ієрархічну систему мереж, звану деревом мереж, можна використати в просторах обмеженої розмірності подвоєння для побудови [en], геометричних кістяків і наближеного розв'язання задачі про найближчих сусідів.
Кристалографія
Для точок у евклідовому просторі множина X є , якщо вона відносно щільна і її різниця Мінковського рівномірно дискретна. Еквівалентно, X є множиною Мейєра, якщо і X і є множиною Делоне. Множини Мейєра названо ім'ям Іва Мейєра, який увів їх (з іншим, але еквівалентним визначенням на основі гармонічного аналізу) як математичну модель для квазікристалів. Вони включають множини точок ґраток, мозаїки Пенроуза і суми Мінковського цих скінченних множин.
Комірки Вороного симетричних множин Делоне утворюють многогранники, що заповнюють простір, які називаються [en].
Див. також
Примітки
- Долбилин, 2016, с. 32.
- Clarkson, 2006, с. 326–335.
- У деяких джерелах назву «-мережа» використовують для структури, яку в цій статті названо «-покриттям». Див., наприклад, статтю Sutherland, 1975
- Сам Делоне називав такі множини системами.
- Долбилин, 2016, с. 32-33.
- Har-Peled, 2004, с. 545–565.
- Har-Peled, Raichel, 2013, с. 605–614.
- Gonzalez, 1985, с. 293–306.
- Har-Peled, Mendel, 2006, с. 1148–1184.
- Har-Peled, Raichel, 2013.
- Krauthgamer, Lee, 2004, с. 798–807.
- Moody, 1997, с. 403–441.
- Grünbaum, Shephard, 1980, с. 951–973.
Література
- Kenneth L. Clarkson. Building triangulations using -nets // STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. — New York : ACM, 2006. — С. 326–335. — . — DOI:
- Sutherland W. A. Introduction to metric and topological spaces. — Oxford University Press, 1975. — С. 110. — .
- Sariel Har-Peled. Clustering motion // . — 2004. — Т. 31, вип. 4. — С. 545–565. — DOI: .
- Har-Peled S., Raichel B. Net and prune: A linear time algorithm for Euclidean distance problems // STOC'13: Proceedings of the 45th Annual ACM Symposium on Theory of Computing. — 2013. — С. 605–614.
- Gonzalez T. F. Clustering to minimize the maximum intercluster distance // Theoretical Computer Science. — 1985. — Т. 38, вип. 2–3. — С. 293–306. — DOI: .
- Har-Peled S., Mendel M. Fast construction of nets in low-dimensional metrics, and their applications // . — 2006. — Т. 35, вип. 5. — С. 1148–1184. — arXiv:cs/0409057. — DOI: .
- Robert Krauthgamer, James R. Lee. Navigating nets: simple algorithms for proximity search // Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '04). — Philadelphia, PA, USA : Society for Industrial and Applied Mathematics, 2004. — С. 798–807. — .
- Robert Moody. Meyer sets and their duals // The Mathematics of Long-Range Aperiodic Order (Waterloo, ON, 1995). — Dordrecht : Kluwer Academic Publishers, 1997. — Т. 489. — С. 403–441. — (NATO Advanced Science Institutes Series C: Mathematical and Physical Sciences)
- Долбилин Н.П. Локально антиподальные множества Делоне // Конференция памяти А.А. Карацубы по теории чисел и приложениям. Сборник аннотаций. — 2016.
- Н. П. Долбилин. Критерий кристалла и локально антиподальные множества Делоне // Вестник ЧелГУ. — 2015. — Вип. 17.
- Grünbaum B., Shephard G. C. Tilings with congruent tiles // Bulletin of the American Mathematical Society. — 1980. — Т. 3, вип. 3. — С. 951–973. — (New Series). — DOI: .
Посилання
- — Tilings Encyclopedia (англ.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U teoriyi metrichnih prostoriv e displaystyle varepsilon merezhi e displaystyle varepsilon pakuvannya e displaystyle varepsilon pokrittya rivnomirno diskretni mnozhini vidnosno shilni mnozhini i mnozhini Delone nazvani im yam radyanskogo matematika Borisa Mikolajovicha Delone ye tisno pov yazanimi viznachennyami mnozhin tochok a radius pakuvannya i radius pokrittya cih mnozhin viznachayut naskilki dobre tochki cih mnozhin rozneseni Ci mnozhini zastosovuyut u teoriyi koduvannya aproksimacijnih algoritmah i teoriyi kvazikristaliv Chervoni tochki utvoryuyut chastinu e displaystyle varepsilon merezhi evklidovoyi ploshini de e displaystyle varepsilon radius velikih zhovtih krugiv Sini krugi polovinnogo radiusa ne peretinayutsya a zhovti pokrivayut usyu ploshinu sho vidpovidaye dvom vimogam viznachennya e displaystyle varepsilon merezhi ViznachennyaYaksho M d metrichnij prostir a X pidmnozhina M to radius pakuvannya mnozhini X ce polovina jogo infimumu vidstanej mizh riznimi tochkami X Yaksho radius pakuvannya dorivnyuye r to vidkriti kuli radiusa r z centrami v tochkah X ne peretinayutsya a bud yaka vidkrita kulya z centrom u tochci z X i radiusom 2r ne mistit inshih tochok X Radius pokrittya mnozhini X ce infimum chisel r takih sho bud yaka tochka M lezhit ne dali nizh na vidstani r prinajmni vid odniyeyi tochki X Tobto ce najmenshij radius takij sho ob yednannya zamknutih kul cogo radiusu z centrami u mnozhini X dorivnyuye prostoru M Mnozhina X ce e displaystyle varepsilon pakuvannya yaksho radius pakuvannya e displaystyle geqslant varepsilon 2 ekvivalentno najmensha vidstan e displaystyle geqslant varepsilon e displaystyle varepsilon pokrittya ce mnozhina X iz radiusom pokrittya e displaystyle leqslant varepsilon a e displaystyle varepsilon merezha ce mnozhina sho ye odnochasno i e displaystyle varepsilon pakuvannyam i e displaystyle varepsilon pokrittyam Mnozhinu nazivayut odnoridno diskretnoyu yaksho vono maye nenulovij radius pakuvannya i vidnosno shilnoyu yaksho maye skinchennij radius pokrittya Mnozhina Delone ce mnozhina sho ye odnochasno odnoridno diskretnoyu i vidnosno shilnoyu Todi bud yaka e displaystyle varepsilon merezha ye mnozhinoyu Delone ale protilezhne hibne Pravilni sistemi ta kristali Mnozhinu Delone nazivayut pravilnoyu sistemoyu yaksho yiyi grupa simetrij G diye tranzitivno na mnozhini X tobto X ye G orbitoyu odniyeyi tochki Mnozhinu Delone nazivayut kristalom yaksho X ye G orbitoyu deyakoyi skinchennoyi mnozhini Pravilna sistema ye vazhlivim okremim vipadkom kristala Na ploshini bud yaka mnozhina Delone v yakij usi 4R okoli ekvivalentni ye pravilnoyu sistemoyu U prostori bud yakoyi rozmirnosti znachennya 4R ne pokrashuyetsya U trivimirnomu prostori bud yaka mnozhina Delone v yakij usi 10R klasteri ekvivalentni ye pravilnoyu sistemoyu U prostori bud yakoyi rozmirnosti ye verhnya ocinka dlya takogo radiusa sho identichnist klasteriv danogo radiusa u mnozhini Delone garantuye yiyi pravilnist Pobudova epsilon merezhDiv takozh Epsilon merezha Cherez viznachennya z najbilshimi obmezhennyami e displaystyle varepsilon merezhi pobuduvati ne prostishe nizh e displaystyle varepsilon pakuvannya e displaystyle varepsilon pokrittya ta mnozhini Delone Odnak yaksho tochki mnozhini M utvoryuyut cilkom uporyadkovanu mnozhinu transfinitna indukciya pokazuye sho mozhna pobuduvati e displaystyle varepsilon merezhu N vklyuchayuchi N kozhnu tochku na yaku infimum vidstanej do mnozhini poperednih tochok u poryadku dorivnyuye prinajmni e displaystyle varepsilon Dlya skinchennoyi mnozhini tochok u evklidovomu prostori obmezhenoyi rozmirnosti kozhnu tochku mozhna pereviriti za stalij chas vidobrazhennyam u gratku komirok diametra e displaystyle varepsilon ta vikoristannyam gesh tablici dlya perevirki yaki susidni komirki vzhe mistyat tochki N Takim chinom e displaystyle varepsilon merezhu mozhna pobuduvati za linijnij chas U zagalnishih skinchennih abo kompaktnih metrichnih prostorah dlya pobudovi skinchennoyi e displaystyle varepsilon merezhi mozhna vikoristati alternativnij algoritm en zasnovanij na en Cej algoritm pochinaye z porozhnoyi merezhi N i dodaye v N najviddalenishu vid N tochku z M dovilno rozrivayuchi zv yazki i zupinyayetsya koli vsi tochki M lezhat na vidstani e displaystyle varepsilon vid N U prostorah obmezhenoyi rozmirnosti podvoyennya algoritm Gonsalesa dlya mnozhin tochok z polinomialnoyu zalezhnistyu mizh najbilshoyu i najmenshoyu vidstannyu mozhna realizuvati z chasom roboti O n log n displaystyle O n log n a takozh realizuvati algoritm nablizhenogo rozv yazannya zadachi z tim samim chasom roboti ta dovilnimi mnozhinami tochok ZastosuvannyaTeoriya koduvannya U teoriyi kodiv z vipravlennyam pomilok metrichnij prostir sho mistit blokovij kod C skladayetsya z ryadkiv fiksovanoyi dovzhini skazhimo n vzyatih za alfavitom rozmiru q mozhna rozglyadati yak vektori z metrikoyu Gemminga Cej prostir poznachayut A q n displaystyle mathcal A q n Radius pokrittya ta radius pakuvannya cogo metrichnogo prostoru pov yazani z mozhlivistyu kodiv koriguvati pomilki Dlya A q n d displaystyle A q n d kodu C pidmnozhina A q n displaystyle mathcal A q n radius pokrittya C ce najmenshe znachennya r take sho bud yakij element A q n displaystyle mathcal A q n mistitsya prinajmni v odnij kuli radiusa r z centrom u kodovomu slovi z C Radius pakuvannya C ce najbilshe znachennya s take sho mnozhina kul radiusa s iz centrami v C poparno ne peretinayutsya Z dovedennya mezhi Gemminga mozhna otrimati sho dlya t 1 2 d 1 displaystyle t left lfloor frac 1 2 d 1 right rfloor maye misce s t r displaystyle s leqslant t leqslant r dd Tomu s r displaystyle s leqslant r i yaksho maye misce rivnist to s r t displaystyle s r t Vipadok rivnosti oznachaye sho dosyagnuto mezhi Gemminga Algoritmi nablizhennya en i Rejchel opisuyut algoritmichnu paradigmu yaku voni nazivayut pobudova merezhi ta obrizannya dlya rozrobki aproksimacijnih algoritmiv dlya geometrichnih zadach optimizaciyi pevnih tipiv viznachenih na mnozhini tochok v evklidovih prostorah Algoritm cogo tipu vklyuchaye taki kroki Vibirayemo vipadkovu tochku p zi mnozhini tochok znahodimo najblizhchogo susida q i vvazhayemo e displaystyle varepsilon rivnim vidstani mizh p i q Pereviryayemo chi e displaystyle varepsilon priblizno bilshe chi menshe vid optimalnogo znachennya vikoristovuyuchi tehniku sho viznachayetsya specifikoyu rozv yazuvanoyi zadachi optimizaciyi Yaksho znachennya bilshe vidalyayemo zi vhidnih danih tochki najblizhchi susidi yakih roztashovani dali nizh na e displaystyle varepsilon Yaksho znachennya menshe buduyemo e displaystyle varepsilon merezhu N i vidalyayemo zi vhidnih danih tochki sho ne nalezhat N V oboh vipadkah ochikuvane chislo tochok sho zalishilisya zmenshuyetsya na stalij mnozhnik tak sho chas roboti viznachayetsya krokom testuvannya Yak voni pokazali taku paradigmu mozhna vikoristati dlya pobudovi shvidkih aproksimacijnih algoritmiv poshuku en poshuku pari tochok zi serednoyu vidstannyu ta deyakih pov yazanih zadach Iyerarhichnu sistemu merezh zvanu derevom merezh mozhna vikoristati v prostorah obmezhenoyi rozmirnosti podvoyennya dlya pobudovi en geometrichnih kistyakiv i nablizhenogo rozv yazannya zadachi pro najblizhchih susidiv Kristalografiya Dlya tochok u evklidovomu prostori mnozhina X ye yaksho vona vidnosno shilna i yiyi riznicya Minkovskogo X X displaystyle X X rivnomirno diskretna Ekvivalentno X ye mnozhinoyu Mejyera yaksho i X i X X displaystyle X X ye mnozhinoyu Delone Mnozhini Mejyera nazvano im yam Iva Mejyera yakij uviv yih z inshim ale ekvivalentnim viznachennyam na osnovi garmonichnogo analizu yak matematichnu model dlya kvazikristaliv Voni vklyuchayut mnozhini tochok gratok mozayiki Penrouza i sumi Minkovskogo cih skinchennih mnozhin Komirki Voronogo simetrichnih mnozhin Delone utvoryuyut mnogogranniki sho zapovnyuyut prostir yaki nazivayutsya en Div takozhMnozhina DanceraPrimitkiDolbilin 2016 s 32 Clarkson 2006 s 326 335 U deyakih dzherelah nazvu e displaystyle varepsilon merezha vikoristovuyut dlya strukturi yaku v cij statti nazvano e displaystyle varepsilon pokrittyam Div napriklad stattyu Sutherland 1975 Sam Delone nazivav taki mnozhini r R displaystyle r R sistemami Dolbilin 2016 s 32 33 Har Peled 2004 s 545 565 Har Peled Raichel 2013 s 605 614 Gonzalez 1985 s 293 306 Har Peled Mendel 2006 s 1148 1184 Har Peled Raichel 2013 Krauthgamer Lee 2004 s 798 807 Moody 1997 s 403 441 Grunbaum Shephard 1980 s 951 973 LiteraturaKenneth L Clarkson Building triangulations using e displaystyle varepsilon nets STOC 06 Proceedings of the 38th Annual ACM Symposium on Theory of Computing New York ACM 2006 S 326 335 ISBN 1595931341 DOI 10 1145 1132516 1132564 Sutherland W A Introduction to metric and topological spaces Oxford University Press 1975 S 110 ISBN 0 19 853161 3 Sariel Har Peled Clustering motion 2004 T 31 vip 4 S 545 565 DOI 10 1007 s00454 004 2822 7 Har Peled S Raichel B Net and prune A linear time algorithm for Euclidean distance problems STOC 13 Proceedings of the 45th Annual ACM Symposium on Theory of Computing 2013 S 605 614 Gonzalez T F Clustering to minimize the maximum intercluster distance Theoretical Computer Science 1985 T 38 vip 2 3 S 293 306 DOI 10 1016 0304 3975 85 90224 5 Har Peled S Mendel M Fast construction of nets in low dimensional metrics and their applications 2006 T 35 vip 5 S 1148 1184 arXiv cs 0409057 DOI 10 1137 S0097539704446281 Robert Krauthgamer James R Lee Navigating nets simple algorithms for proximity search Proceedings of the 15th Annual ACM SIAM Symposium on Discrete Algorithms SODA 04 Philadelphia PA USA Society for Industrial and Applied Mathematics 2004 S 798 807 ISBN 0 89871 558 X Robert Moody Meyer sets and their duals The Mathematics of Long Range Aperiodic Order Waterloo ON 1995 Dordrecht Kluwer Academic Publishers 1997 T 489 S 403 441 NATO Advanced Science Institutes Series C Mathematical and Physical Sciences Dolbilin N P Lokalno antipodalnye mnozhestva Delone Konferenciya pamyati A A Karacuby po teorii chisel i prilozheniyam Sbornik annotacij 2016 N P Dolbilin Kriterij kristalla i lokalno antipodalnye mnozhestva Delone Vestnik ChelGU 2015 Vip 17 Grunbaum B Shephard G C Tilings with congruent tiles Bulletin of the American Mathematical Society 1980 T 3 vip 3 S 951 973 New Series DOI 10 1090 S0273 0979 1980 14827 2 Posilannya Tilings Encyclopedia angl