Набор Делоне

В математической теории метрических пространств , $ε$ сети - $ε$ -упаковки , $ε$ -покрытия , равномерно дискретные множества , относительно плотные множества и множества Делоне (названные в честь Бориса Делоне ) — это несколько тесно связанных определений хорошо расположенных множеств точек. а радиус упаковки и радиус покрытия этих наборов измеряют, насколько хорошо они расположены. Эти множества имеют приложения в теории кодирования , аппроксимационных алгоритмах и теории квазикристаллов .

Определения

Если $(M, d)$ — метрическое пространство, а $—$ M $,$ то радиус упаковки r $X$ X $X.$ равен половине наименьшего расстояния между отдельными $подмножество$ членами Открытые шары радиуса $r$ с центрами в точках $X$ не будут пересекаться друг с другом. Радиус покрытия R $M$ X $R$ — это наименьшее расстояние, на котором каждая точка $находится$ на расстоянии $хотя$ бы от одной точки $X$ ; то есть $R$ - наименьший радиус, такой, что замкнутые шары этого радиуса с центрами в точках $X$ имеют все $M$ как свое объединение.

ε $X$ -упаковкой называется множество $радиуса$ упаковки $r ≥ .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ ε / 2 ⁠$ (эквивалентно минимальное расстояние $\geq ε$ ), $ε$ -покрытие — это множество $X$ радиуса покрытия $R \leq ε$ , а $ε$ -сеть — это множество, которое является одновременно $ε$ -упаковкой и $ε$ -покрытием ( $⁠ ε / 2 ⁠ \leq р \leq р \leq ε$ ).

Множество является равномерно дискретным , если оно имеет ненулевой радиус упаковки ( $0 < r$ ), и относительно плотным , если оно имеет конечный радиус покрытия ( $R < \infty$ ).

Множество Делоне — это множество, которое одновременно равномерно дискретно и относительно плотно ( $0 < r \leq R < \infty$ ). Таким образом, каждая $ε$ -сеть является Делоне, но не наоборот. ^{[ 1 ]}^{[ 2 ]}

Построение ε -сетей

Как наиболее ограничительное из приведенных выше определений, $ε$ -сети построить по крайней мере так же сложно, как $ε$ -упаковки, $ε$ -покрытия и множества Делоне. Однако всякий раз, когда точки $M$ имеют хороший порядок , трансфинитная индукция показывает, что можно построить $ε$ -сеть $N$ , включая в $N$ каждую точку, для которой нижняя грань расстояний до множества более ранних точек упорядочения равна по крайней мере $ε$ . Для конечных наборов точек в евклидовом пространстве ограниченной размерности каждая точка может быть проверена за постоянное время путем сопоставления ее с сеткой ячеек диаметра $ε$ и использования хеш-таблицы для проверки того, какие соседние ячейки уже содержат точки $N$ ; таким образом, в этом случае $ε$ -сеть может быть построена за линейное время . ^{[ 3 ]}^{[ 4 ]}

Для более общих конечных или компактных -сети можно использовать альтернативный алгоритм Тео Гонсалеса, основанный на самом дальнем обходе метрических пространств для построения конечной $ε$ . Этот алгоритм инициализирует сеть $N$ пустой, а затем неоднократно добавляет к $N$ самую дальнюю точку в $M$ от $N$ произвольно разрывая связи и останавливаясь, когда все точки $M$ находятся на расстоянии $ε$ от $N.$ , ^{[ 5 ]} В пространствах ограниченной удвоенной размерности алгоритм Гонсалеса может быть реализован за $время O(n log n)$ для наборов точек с полиномиальным соотношением между их самым дальним и ближайшим расстояниями и аппроксимирован за то же время с привязкой для произвольных наборов точек. ^{[ 6 ]}

Приложения

Теория кодирования

В теории кодов, исправляющих ошибки , метрическое пространство, содержащее блочный код $C,$ состоит из строк фиксированной длины, скажем, $n$ , взятых по алфавиту размера $q$ (их можно рассматривать как векторы ), с метрикой Хэмминга . Это пространство обозначается ⁠ ${\mathcal {A}}_{q}^{n}.$ ⁠ Радиус покрытия и радиус упаковки этого метрического пространства связаны со способностью кода исправлять ошибки. Примером может служить игра с переключением Берлекэмпа .

Алгоритмы аппроксимации

Хар-Пелед и Райхель (2013) описывают алгоритмическую парадигму, которую они называют «сеткой и обрезкой», для разработки алгоритмов аппроксимации для определенных типов задач геометрической оптимизации, определенных на наборах точек в евклидовых пространствах . Алгоритм этого типа работает, выполняя следующие шаги:

Выберите случайную точку $p$ из набора точек, найдите ее ближайшего соседа $q$ и установите $ε$ как расстояние между $p$ и $q$ .
Проверьте, является ли ε (приблизительно) больше или меньше значения оптимального решения (используя метод, специфичный для конкретной решаемой задачи оптимизации).
- Если оно больше, удалите из входных данных точки, ближайший сосед которых находится дальше, чем $ε$
- Если оно меньше, постройте $ε$ -сеть $N$ и удалите из входа точки, которых нет $N.$ в

В обоих случаях ожидаемое количество оставшихся баллов уменьшается в постоянном коэффициенте, поэтому во времени доминирует этап тестирования. Как они показывают, эту парадигму можно использовать для построения алгоритмов быстрой аппроксимации для кластеризации k-центров , поиска пары точек со средним расстоянием и ряда связанных с этим задач.

Иерархическая система сетей, называемая сетевым деревом , может использоваться в пространствах ограниченной удвоенной размерности для построения хорошо разделенных парных разложений , геометрических гаек и аппроксимации ближайших соседей . ^{[ 6 ]}^{[ 7 ]}

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

Для точек евклидова пространства множество $X$ является множеством Мейера , если оно относительно плотное и его разностное множество $X - X$ равномерно дискретно. Эквивалентно, $X$ является множеством Мейера, если и $X$ , и $X - X$ являются множествами Делоне. Мейерские множества названы в честь Ива Мейера , который представил их (с другим, но эквивалентным определением, основанным на гармоническом анализе ) как математическую модель квазикристаллов . Они включают точечные множества решеток , разбиения Пенроуза и суммы Минковского этих множеств с конечными множествами. ^{[ 8 ]}

Ячейки Вороного симметричных множеств Делоне образуют заполняющие пространство многогранники, называемые плезиоэдрами . ^{[ 9 ]}

См. также

Танцор набор

Ссылки

^ Кларксон, Кеннет Л. (2006), «Построение триангуляции с использованием ε -сетей», STOC'06: Материалы 38-го ежегодного симпозиума ACM по теории вычислений , Нью-Йорк: ACM, стр. 326–335, doi : 10.1145/1132516.1132564 , ISBN 1595931341 , МР 2277158 , S2CID 14132888 .
^ В некоторых источниках используется « $ε$ -сеть» для того, что здесь называется « $ε$ -покрытием»; см., например Сазерленд, Вашингтон (1975), Введение в метрические и топологические пространства , Oxford University Press, стр. 110, ISBN 0-19-853161-3 , Збл 0304.54002 .
^ Хар-Пелед, С. (2004), «Кластерное движение», Дискретная и вычислительная геометрия , 31 (4): 545–565, doi : 10.1007/s00454-004-2822-7 , MR 2053498 .
^ Хар-Пелед, С.; Райчел, Б. (2013), «Сеть и обрезка: алгоритм линейного времени для задач евклидова расстояния», STOC'13: Материалы 45-го ежегодного симпозиума ACM по теории вычислений , стр. 605–614, arXiv : 1409.7425 .
^ Гонсалес, Т.Ф. (1985), «Кластеризация для минимизации максимального расстояния между кластерами», Theoretical Computer Science , 38 (2–3): 293–306, doi : 10.1016/0304-3975(85)90224-5 , MR 0807927 .
^ Jump up to: ^а ^б Хар-Пелед, С.; Мендель, М. (2006), «Быстрое построение сетей в низкоразмерных метриках и их приложения», SIAM Journal on Computing , 35 (5): 1148–1184, arXiv : cs/0409057 , doi : 10.1137/S0097539704446281 , МИСТЕР 2217141 , S2CID 37346335 .
^ Краутгамер, Роберт; Ли, Джеймс Р. (2004), «Навигационные сети: простые алгоритмы поиска близости», Труды 15-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '04) , Филадельфия, Пенсильвания, США: Общество промышленной и прикладной математики , стр. 798–807, ISBN. 0-89871-558-Х .
^ Муди, Роберт В. (1997), «Множества Мейера и их двойники», Математика дальнего апериодического порядка (Ватерлоо, Онтарио, 1995) , Серия C Институтов передовых научных исследований НАТО: Математические и физические науки, том. 489, Дордрехт: Kluwer Academic Publishers, стр. 403–441, MR 1460032 , заархивировано из оригинала 03 марта 2016 г. , получено 10 июля 2013 г.
^ Грюнбаум, Бранко ; Шепард, GC (1980), «Плитки с конгруэнтными плитками», Бюллетень Американского математического общества , новая серия, 3 (3): 951–973, doi : 10.1090/S0273-0979-1980-14827-2 , MR 0585178 .

Внешние ссылки

Набор Делоне — Энциклопедия Tilings

[1] Кларксон, Кеннет Л. (2006), «Построение триангуляции с использованием ε -сетей», STOC'06: Материалы 38-го ежегодного симпозиума ACM по теории вычислений , Нью-Йорк: ACM, стр. 326–335, doi : 10.1145/1132516.1132564 , ISBN 1595931341 , МР 2277158 , S2CID 14132888 .

[2] В некоторых источниках используется « $ε$ -сеть» для того, что здесь называется « $ε$ -покрытием»; см., например Сазерленд, Вашингтон (1975), Введение в метрические и топологические пространства , Oxford University Press, стр. 110, ISBN 0-19-853161-3 , Збл 0304.54002 .

[3] Хар-Пелед, С. (2004), «Кластерное движение», Дискретная и вычислительная геометрия , 31 (4): 545–565, doi : 10.1007/s00454-004-2822-7 , MR 2053498 .

[4] Хар-Пелед, С.; Райчел, Б. (2013), «Сеть и обрезка: алгоритм линейного времени для задач евклидова расстояния», STOC'13: Материалы 45-го ежегодного симпозиума ACM по теории вычислений , стр. 605–614, arXiv : 1409.7425 .

[5] Гонсалес, Т.Ф. (1985), «Кластеризация для минимизации максимального расстояния между кластерами», Theoretical Computer Science , 38 (2–3): 293–306, doi : 10.1016/0304-3975(85)90224-5 , MR 0807927 .

[HM06-6] Jump up to: ^а ^б Хар-Пелед, С.; Мендель, М. (2006), «Быстрое построение сетей в низкоразмерных метриках и их приложения», SIAM Journal on Computing , 35 (5): 1148–1184, arXiv : cs/0409057 , doi : 10.1137/S0097539704446281 , МИСТЕР 2217141 , S2CID 37346335 .

[7] Краутгамер, Роберт; Ли, Джеймс Р. (2004), «Навигационные сети: простые алгоритмы поиска близости», Труды 15-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '04) , Филадельфия, Пенсильвания, США: Общество промышленной и прикладной математики , стр. 798–807, ISBN. 0-89871-558-Х .

[8] Муди, Роберт В. (1997), «Множества Мейера и их двойники», Математика дальнего апериодического порядка (Ватерлоо, Онтарио, 1995) , Серия C Институтов передовых научных исследований НАТО: Математические и физические науки, том. 489, Дордрехт: Kluwer Academic Publishers, стр. 403–441, MR 1460032 , заархивировано из оригинала 03 марта 2016 г. , получено 10 июля 2013 г.

[9] Грюнбаум, Бранко ; Шепард, GC (1980), «Плитки с конгруэнтными плитками», Бюллетень Американского математического общества , новая серия, 3 (3): 951–973, doi : 10.1090/S0273-0979-1980-14827-2 , MR 0585178 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]