Диаграмма зон
![]() | Эта статья требует внимания специалиста по математике . Конкретная проблема заключается в следующем: похоже, это противоречит WP:NOTHOWTO , и эксперт может решить эту проблему. ( ноябрь 2022 г. ) |
Диаграмма зон — это некий геометрический объект, являющийся разновидностью понятия диаграммы Вороного . Его представили Тецуо Асано , Иржи Матушек и Такеши Токуяма в 2007 году. [1]
Формально это неподвижная точка некоторой функции. Его существование или уникальность заранее не ясны и устанавливаются лишь в конкретных случаях. Его вычисление также не очевидно.
Частный, но информативный случай
[ редактировать ]Рассмотрим группу из разные точки в евклидовой плоскости . Каждая точка называется площадкой. Когда мы говорим о диаграмме Вороного, индуцированной этими узлами, мы ассоциируем с узлом набор всех точек плоскости, расстояние которых до данного узла не больше их расстояния до любого другого места . Коллекция Одной из этих областей является диаграмма Вороного, связанная с этими сайтами, и она вызывает разложение плоскости на области: области Вороного (ячейки Вороного).
На диаграмме зон — регион, связанный с сайтом. определяется немного по-другому: вместо того, чтобы ассоциировать его, набор всех точек, расстояние до которых не больше, чем их расстояние до других сайтов, мы связываем их с набор всех точек плоскости, расстояние до которых не больше, чем их расстояние до любого другого региона. Формально,
- .
Здесь обозначает евклидово расстояние между точками и и это расстояние между точкой и набор . Кроме того, так как мы рассматриваем самолет. Кортеж — это диаграмма зон, связанная с сайтами.
Проблема с этим определением в том, что оно кажется замкнутым: чтобы знать мы должны знать для каждого индекса но каждый такой определяется с точки зрения . Если подумать, мы видим, что на самом деле кортеж является решением следующей системы уравнений:
Строго говоря, зонной диаграммой называется любое решение этой системы, если такое решение существует. Это определение может быть расширено без каких-либо существенных изменений на более высокие измерения, на узлы, которые не обязательно являются точками, на бесконечное число узлов и т. д.
Интерпретация
[ редактировать ]В некоторых ситуациях, таких как описанная выше, диаграмму зон можно интерпретировать как определенное равновесие между взаимно враждебными королевствами. [1] [2] В дискретной ситуации ее можно интерпретировать как устойчивую конфигурацию в некоторой комбинаторной игре. [2]
Формальное определение
[ редактировать ]Позволять — метрическое пространство и пусть быть набором как минимум из 2 элементов (индексов), возможно, бесконечным. Учитывая кортеж непустых подмножеств , называемые сайтами, диаграмма зон относительно этого кортежа представляет собой кортеж подмножеств такой, что для всех выполняется следующее уравнение:
Диаграмма зон как фиксированная точка
[ редактировать ]Система уравнений, определяющая диаграмму зон, может быть представлена как фиксированная точка функции, определенной в пространстве продукта. Действительно, для каждого индекса позволять — множество всех непустых подмножеств .Позволять
и пусть быть функцией, определяемой , где и
Затем является диаграммой зон тогда и только тогда, когда она является фиксированной точкой Dom , то есть . Просмотр диаграмм зон в виде фиксированных точек полезен, поскольку в некоторых случаях известные инструменты или подходы из теории фиксированных точек для их исследования можно использовать .получение соответствующих свойств (существования и т.п.).
Существование и уникальность
[ редактировать ]После новаторской работы Асано и др. [1] (существование и единственность зонной диаграммы в евклидовой плоскости относительно конечного числа точечных узлов) было опубликовано несколько результатов о существовании или существовании и единственности. По состоянию на 2012 год наиболее общие опубликованные результаты:
- 2 сайта (существование): существует хотя бы одна диаграмма зон для любой пары произвольных сайтов в любом метрическом пространстве . Фактически, этот результат существования справедлив в любом m-пространстве [2] (обобщение метрического пространства , в котором, например, функция расстояния может быть отрицательной и не удовлетворять неравенству треугольника).
- Более двух узлов (существование): существует зонная диаграмма конечного числа компактных и непересекающихся узлов, содержащихся внутри компактного и выпуклого подмножества пространства равномерно выпуклого . Этот результат действительно справедлив и в более общей ситуации. [3]
- Более двух сайтов (существование и уникальность): существует уникальная диаграмма зон относительно любого набора (возможно, бесконечного) замкнутых и положительно разделенных сайтов в любом конечномерном евклидовом пространстве . Положительное разделение означает, что существует положительная нижняя граница расстояния между любыми двумя узлами. Аналогичный результат сформулирован для случая, когда нормированное пространство конечномерно и одновременно равномерно выпукло и равномерно гладко. [4]
- неединственность : известны простые примеры даже для случая двух точечных сайтов. [2] [4]
Вычисление
[ редактировать ]Требуется дополнительная информация.
Связанные объекты и возможные применения
[ редактировать ]Помимо диаграмм Вороного , диаграммы зон тесно связаны с другими геометрическими объектами, такими как диаграммы двойных зон . [2] трисектора , [5] k-секторов , [6] диаграммы смягченных зон [7] и, как следствие, может использоваться для решения задач, связанных с движением робота и проектированием СБИС. [5] [6]
Ссылки
[ редактировать ]- ^ Jump up to: а б с Асано, Тецуо ; Матушек, Иржи ; Токуяма, Такеши (2007). «Диаграммы зон: существование, уникальность и алгоритмическая задача». SIAM Journal по вычислительной технике . 37 (4): 1182–1198. дои : 10.1137/06067095X . Предварительная версия в Proc. СОДА 2007, стр. 756-765.
- ^ Jump up to: а б с д и Рим, Дэниел; Райх, Симеон (2009). «Зональные и двойные зональные диаграммы в абстрактных пространствах». Коллоквиум Математикум . 115 : 129–145. arXiv : 0708.2668 . дои : 10,4064/см115-1-11 .
- ^ Копецкая, Ева; Рим, Дэниел; Райх, Симеон (2012). «Диаграммы зон в компактных подмножествах равномерно выпуклых нормированных пространств». Израильский математический журнал . 188 : 1–23. arXiv : 1002.3583 . дои : 10.1007/s11856-011-0094-5 . Предварительные версии в Proc. CCCG 2010, стр. 17-20.
- ^ Jump up to: а б Кавамура, Акитоши; Матушек, Иржи ; Токуяма, Такеши (2012). «Диаграммы зон в евклидовых пространствах и других нормированных пространствах». Математические Аннален . 354 : 1201–1221. arXiv : 0912.3016 . дои : 10.1007/s00208-011-0761-1 . Предварительная версия в Proc. СоКГ 2010, стр. 216-221.
- ^ Jump up to: а б Асано, Тецуо ; Матушек, Иржи ; Токуяма, Такеши (2007). «Трисекторная кривая расстояний» . Достижения в математике . 212 : 338–360. дои : 10.1016/j.aim.2006.10.006 . Предварительная версия в Proc. СТОК 2006, стр. 336–343.
- ^ Jump up to: а б Имаи, Кейко; Кавамура, Акитоши; Матушек, Иржи ; Токуяма, Такеши; Рим, Дэниел; Токуяма, Такеши (2010). «Дистанции k-секторов существуют» . Вычислительная геометрия . 43 (9): 713–720. arXiv : 0912.4164 . дои : 10.1016/j.comgeo.2010.05.001 . Предварительные версии в Proc. SoCG 2010, стр. 210–215.
- ^ Биази, Серджио К.; Калантари, Бахман; Калантари, Ирадж (2011). «Диаграммы смягченных зон и их расчет». Труды по вычислительной технике XIV . Конспекты лекций по информатике. Том. 6970. стр. 31–59. дои : 10.1007/978-3-642-25249-5_2 . ISBN 978-3-642-25248-8 . Предварительная версия в Proc. ИСВД 2010, стр. 171--180.