Из Википедии, свободной энциклопедии
  (Перенаправлен из Равномерно дискретного набора )
Перейти к навигации Перейти к поиску
Красные точки образуют часть ε-сети для евклидовой плоскости, где ε - радиус больших желтых дисков. Синие диски с половиной радиуса не пересекаются, а желтые диски вместе покрывают всю плоскость, удовлетворяя двум требованиям определения ε-сети.

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

Определения [ править ]

Если ( М , д ) является метрическим пространством, а Х представляют собой подмножество М , то радиус упаковки из X составляет половина от инфимума расстояний между различными членами X . Если радиус упаковки равен r , то открытые шары радиуса r с центрами в точках X будут не пересекаться друг с другом, и каждый открытый шар с центром в одной из точек X с радиусом 2 r будет не пересекаться с остальной частью. X . Радиус покрытия из X является нижней гранью чиселr такое, что каждая точка M находится на расстоянии r по крайней мере от одной точки в X ; то есть это наименьший радиус, такой что замкнутые шары этого радиуса с центрами в точках X имеют все M в качестве своего объединения. Ε -упаковка представляет собой набор Х упаковок радиуса ≥  е / 2 (эквивалентно, минимальное расстояние ≥ е), ε-покрытие представляет собой набор Х покрытий радиуса ≤  е , а ε-сеть представляет собой набор , который является одновременно ε -упаковка и ε- покрытие. Множество равномерно дискретноеесли он имеет ненулевой радиус упаковки, и относительно плотный, если он имеет конечный радиус покрытия. Набор Делоне - это набор, который одновременно является равномерно дискретным и относительно плотным; таким образом, каждая ε -сеть является Делоне, но не наоборот. [1] [2]

Построение ε-сетей [ править ]

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

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

Приложения [ править ]

Теория кодирования [ править ]

Основная статья: граница Хэмминга § Радиус покрытия и радиус упаковки

В теории кодов с исправлением ошибок метрическое пространство, содержащее блочный код C, состоит из строк фиксированной длины, скажем n , взятых по алфавиту размера q (их можно рассматривать как векторы ) с метрикой Хэмминга . Это пространство обозначается . Радиус покрытия и радиус упаковки этого метрического пространства связаны со способностью кода исправлять ошибки.

Алгоритмы аппроксимации [ править ]

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

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

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

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

Кристаллография [ править ]

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

В клетках Вороных симметричных множеств Делона образуют пространство заполнения многогранников под названием plesiohedra . [9]

См. Также [ править ]

  • Набор Danzer

Ссылки [ править ]

  1. ^ Clarkson, Kenneth L. (2006), "Построение триангуляции с использованием ε -сетями", STOC'06: Труды 38 - й ежегодный симпозиум ACM по теории вычислений , Нью - Йорк.: АКМ, С. 326-335, DOI : 10.1145 / 1132516.1132564 , ISBN 1595931341, MR  2277158.
  2. ^ Некоторые источники используют " ε- сеть" для того, что здесь называется " ε- покрытием"; см., например, Сазерленд, Вашингтон (1975), Введение в метрические и топологические пространства , Oxford University Press, с. 110, ISBN 0-19-853161-3, Zbl  0304,54002.
  3. ^ Хар-Пелед, С. (2004), "Кластеризация движения", Дискретные и Вычислительная геометрия , 31 (4): 545-565, DOI : 10.1007 / s00454-004-2822-7 , МР 2053498 .
  4. ^ Har-Peled, S .; Райчел, Б. (2013), "Сеть и обрезка: алгоритм линейного времени для задач евклидова расстояния", STOC'13: Материалы 45-го ежегодного симпозиума ACM по теории вычислений , стр. 605–614, arXiv : 1409.7425.
  5. ^ Гонсалес, TF (1985), «Кластеризация для минимизации максимального межкластерного расстояния», Теоретическая информатика , 38 (2–3): 293–306, DOI : 10.1016 / 0304-3975 (85) 90224-5 , MR 0807927 .
  6. ^ a b Har-Peled, S .; Мендель, М. (2006), «Быстрое построение сетей в низкоразмерных метриках и их приложениях», SIAM Journal on Computing , 35 (5): 1148–1184, arXiv : cs / 0409057 , doi : 10.1137 / S0097539704446281 , Руководство по ремонту 2217141 .
  7. ^ Krauthgamer, Роберт; Ли, Джеймс Р. (2004), «Навигация в сетях: простые алгоритмы поиска по близости», Труды 15-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '04) , Филадельфия, Пенсильвания, США: Общество промышленной и прикладной математики , стр. 798–807, ISBN 0-89871-558-X.
  8. ↑ Муди, Роберт В. (1997), «Множества Мейера и их двойники», Математика дальнего апериодического порядка (Ватерлоо, ОН, 1995) , НАТО Advanced Science Institutes Series C: Mathematical and Physical Sciences, 489 , Dordrecht: Kluwer Academic Publishers, стр. 403–441, MR 1460032. .
  9. ^ Грюнбаум, Бранко ; Шеппард, GC (1980), "Замощение с конгруэнтной плиткой", Бюллетень Американского математического общества , Новой серия, 3 (3): 951-973, DOI : 10,1090 / S0273-0979-1980-14827-2 , MR 0585178 .

Внешние ссылки [ править ]

  • Набор Delone - энциклопедия Tilings