Множина Делоне

У теорії метричних просторів, $\varepsilon$-мережі, $\varepsilon$-пакування, $\varepsilon$-покриття, рівномірно дискретні множини, відносно щільні множини і множини Делоне (названі ім'ям радянського математика Бориса Миколайовича Делоне) є тісно пов'язаними визначеннями множин точок, а радіус пакування і радіус покриття цих множин визначають, наскільки добре точки цих множин рознесені. Ці множини застосовують у теорії кодування, апроксимаційних алгоритмах і теорії квазікристалів.

Червоні точки утворюють частину $\varepsilon$-мережі евклідової площини, де $\varepsilon$ — радіус великих жовтих кругів. Сині круги половинного радіуса не перетинаються, а жовті покривають усю площину, що відповідає двом вимогам визначення $\varepsilon$-мережі.

Визначення

Якщо (M,d) — метричний простір, а X — підмножина M, то радіус пакування множини X — це половина його інфімуму відстаней між різними точками X. Якщо радіус пакування дорівнює r, то відкриті кулі радіуса r з центрами в точках X не перетинаються, а будь-яка відкрита куля з центром у точці з X і радіусом 2r не містить інших точок X. Радіус покриття множини X — це інфімум чисел r, таких що будь-яка точка M лежить не далі ніж на відстані r принаймні від однієї точки X. Тобто це найменший радіус, такий, що об'єднання замкнутих куль цього радіусу з центрами у множині X дорівнює простору M. Множина X — це $\varepsilon$-пакування, якщо радіус пакування $\geqslant \varepsilon$/2 (еквівалентно, найменша відстань $\geqslant \varepsilon$), $\varepsilon$-покриття — це множина X із радіусом покриття $\leqslant \varepsilon$, а $\varepsilon$-мережа — це множина, що є одночасно і $\varepsilon$-пакуванням, і $\varepsilon$ -покриттям. Множину називають однорідно дискретною, якщо воно має ненульовий радіус пакування і відносно щільною, якщо має скінченний радіус покриття. Множина Делоне — це множина, що є одночасно однорідно дискретною, і відносно щільною. Тоді будь-яка $\varepsilon$-мережа є множиною Делоне, але протилежне хибне.

Правильні системи та кристали

Множину Делоне називають правильною системою, якщо її група симетрій G діє транзитивно на множині X (тобто X є G-орбітою однієї точки). Множину Делоне називають кристалом, якщо X є G-орбітою деякої скінченної множини. Правильна система є важливим окремим випадком кристала.

1. На площині будь-яка множина Делоне, в якій усі 4R-околи еквівалентні, є правильною системою.
2. У просторі будь-якої розмірності значення 4R не покращується.
3. У тривимірному просторі будь-яка множина Делоне, в якій усі 10R-кластери еквівалентні, є правильною системою.
4. У просторі будь-якої розмірності є верхня оцінка для такого радіуса, що ідентичність кластерів даного радіуса у множині Делоне гарантує її правильність.

Побудова епсилон-мереж

Через визначення з найбільшими обмеженнями, $\varepsilon$-мережі побудувати не простіше ніж $\varepsilon$-пакування, $\varepsilon$-покриття та множини Делоне. Однак, якщо точки множини M утворюють цілком упорядковану множину, трансфінітна індукція показує, що можна побудувати $\varepsilon$-мережу N, включаючи N кожну точку, на яку інфімум відстаней до множини попередніх точок у порядку дорівнює принаймні $\varepsilon$. Для скінченної множини точок у евклідовому просторі обмеженої розмірності кожну точку можна перевірити за сталий час відображенням у ґратку комірок діаметра $\varepsilon$ та використанням геш-таблиці для перевірки, які сусідні комірки вже містять точки N. Таким чином, $\varepsilon$-мережу можна побудувати за лінійний час.

У загальніших скінченних або компактних метричних просторах для побудови скінченної $\varepsilon$-мережі можна використати альтернативний алгоритм Теофіло Гонсалеса, заснований на виборі найвіддаленіших точок. Цей алгоритм починає з порожньої мережі N і додає в N найвіддаленішу від N точку з M, довільно розриваючи зв'язки, і зупиняється, коли всі точки M лежать на відстані $\varepsilon$ від N. У просторах обмеженої розмірності подвоєння алгоритм Гонсалеса для множин точок з поліноміальною залежністю між найбільшою і найменшою відстанню можна реалізувати з часом роботи $O(n\log n)$, а також реалізувати алгоритм наближеного розв'язання задачі з тим самим часом роботи та довільними множинами точок.

Застосування

Теорія кодування

У теорії кодів з виправленням помилок метричний простір, що містить блоковий код C, складається з рядків фіксованої довжини, скажімо, n, взятих за алфавітом розміру q (можна розглядати як вектори) з метрикою Геммінга. Цей простір позначають ${\mathcal {A}}_{q}^{n}$. Радіус покриття та радіус пакування цього метричного простору пов'язані з можливістю кодів коригувати помилки.

Для $A_{q}(n,d)$ коду C (підмножина ${\mathcal {A}}_{q}^{n}$), радіус покриття C — це найменше значення r, таке, що будь-який елемент ${\mathcal {A}}_{q}^{n}$ міститься принаймні в одній кулі радіуса r з центром у кодовому слові з C. Радіус пакування C — це найбільше значення s, таке, що множина куль радіуса s із центрами в C попарно не перетинаються. З доведення межі Геммінга можна отримати, що для $t\,=\,\left\lfloor {\frac {1}{2}}(d-1)\right\rfloor$ має місце

$s\leqslant t\leqslant r$.

Тому, $s\leqslant r$ і, якщо має місце рівність, то $s=r=t$. Випадок рівності означає, що досягнуто межі Геммінга.

Алгоритми наближення

Хар-Пелед і Рейчел описують алгоритмічну парадигму, яку вони називають «побудова мережі та обрізання» для розробки апроксимаційних алгоритмів для геометричних задач оптимізації певних типів, визначених на множині точок в евклідових просторах. Алгоритм цього типу включає такі кроки:

1. Вибираємо випадкову точку p зі множини точок, знаходимо найближчого сусіда q і вважаємо $\varepsilon$ рівним відстані між p і q.
2. Перевіряємо, чи $\varepsilon$ (приблизно) більше, чи менше від оптимального значення (використовуючи техніку, що визначається специфікою розв'язуваної задачі оптимізації)
   • Якщо значення більше, видаляємо зі вхідних даних точки, найближчі сусіди яких розташовані далі, ніж на $\varepsilon$
   • Якщо значення менше, будуємо $\varepsilon$-мережу N і видаляємо зі вхідних даних точки, що не належать N.

В обох випадках очікуване число точок, що залишилися, зменшується на сталий множник, так що час роботи визначається кроком тестування. Як вони показали, таку парадигму можна використати для побудови швидких апроксимаційних алгоритмів пошуку k-центра, пошуку пари точок зі середньою відстанню та деяких пов'язаних задач.

Ієрархічну систему мереж, звану деревом мереж, можна використати в просторах обмеженої розмірності подвоєння для побудови цілком розділених декомпозиційних пар, геометричних кістяків і наближеного розв'язання задачі про найближчих сусідів.

Кристалографія

Для точок у евклідовому просторі множина X є множиною Мейєра, якщо вона відносно щільна і її різниця Мінковського $X-X$ рівномірно дискретна. Еквівалентно, X є множиною Мейєра, якщо і X і $X-X$ є множиною Делоне. Множини Мейєра названо ім'ям Іва Мейєра, який увів їх (з іншим, але еквівалентним визначенням на основі гармонічного аналізу) як математичну модель для квазікристалів. Вони включають множини точок ґраток, мозаїки Пенроуза і суми Мінковського цих скінченних множин.

Комірки Вороного симетричних множин Делоне утворюють многогранники, що заповнюють простір, які називаються плезіоедрами.

Див. також

• Множина Данцера

Література

• Kenneth L. Clarkson. Building triangulations using $\varepsilon$-nets // STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. — New York : ACM, 2006. — С. 326–335. — ISBN 1595931341. — DOI:10.1145/1132516.1132564.
• Sutherland W. A. Introduction to metric and topological spaces. — Oxford University Press, 1975. — С. 110. — ISBN 0-19-853161-3.
• Sariel Har-Peled. Clustering motion // Discrete and Computational Geometry. — 2004. — Т. 31, вип. 4. — С. 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. — С. 605–614.
• Gonzalez T. F. Clustering to minimize the maximum intercluster distance // Theoretical Computer Science. — 1985. — Т. 38, вип. 2–3. — С. 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 // SIAM Journal on Computing. — 2006. — Т. 35, вип. 5. — С. 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. — С. 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. — Т. 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:10.1090/S0273-0979-1980-14827-2.

Посилання

• Delone set — Tilings Encyclopedia (англ.)