Jump to content

Диаграмма зон

Диаграмма зон — это некий геометрический объект, являющийся разновидностью понятия диаграммы Вороного . Его представили Тецуо Асано , Иржи Матушек и Такеши Токуяма в 2007 году. [1]

Формально это неподвижная точка некоторой функции. Его существование или уникальность заранее не ясны и устанавливаются лишь в конкретных случаях. Его вычисление также не очевидно.

Частный, но информативный случай

[ редактировать ]

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

На диаграмме зон — регион, связанный с сайтом. определяется немного по-другому: вместо того, чтобы ассоциировать его, набор всех точек, расстояние до которых не больше, чем их расстояние до других сайтов, мы связываем их с набор всех точек плоскости, расстояние до которых не больше, чем их расстояние до любого другого региона. Формально,

.

Здесь обозначает евклидово расстояние между точками и и это расстояние между точкой и набор . Кроме того, так как мы рассматриваем самолет. Кортеж — это диаграмма зон, связанная с сайтами.

Проблема с этим определением в том, что оно кажется замкнутым: чтобы знать мы должны знать для каждого индекса но каждый такой определяется с точки зрения . Если подумать, мы видим, что на самом деле кортеж является решением следующей системы уравнений:

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

Интерпретация

[ редактировать ]

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

Формальное определение

[ редактировать ]

Позволять метрическое пространство и пусть быть набором как минимум из 2 элементов (индексов), возможно, бесконечным. Учитывая кортеж непустых подмножеств , называемые сайтами, диаграмма зон относительно этого кортежа представляет собой кортеж подмножеств такой, что для всех выполняется следующее уравнение:

Диаграмма зон как фиксированная точка

[ редактировать ]

Система уравнений, определяющая диаграмму зон, может быть представлена ​​как фиксированная точка функции, определенной в пространстве продукта. Действительно, для каждого индекса позволять — множество всех непустых подмножеств .Позволять

и пусть быть функцией, определяемой , где и

Затем является диаграммой зон тогда и только тогда, когда она является фиксированной точкой Dom , то есть . Просмотр диаграмм зон в виде фиксированных точек полезен, поскольку в некоторых случаях известные инструменты или подходы из теории фиксированных точек для их исследования можно использовать .получение соответствующих свойств (существования и т.п.).

Существование и уникальность

[ редактировать ]

После новаторской работы Асано и др. [1] (существование и единственность зонной диаграммы в евклидовой плоскости относительно конечного числа точечных узлов) было опубликовано несколько результатов о существовании или существовании и единственности. По состоянию на 2012 год наиболее общие опубликованные результаты:

  • 2 сайта (существование): существует хотя бы одна диаграмма зон для любой пары произвольных сайтов в любом метрическом пространстве . Фактически, этот результат существования справедлив в любом m-пространстве [2] (обобщение метрического пространства , в котором, например, функция расстояния может быть отрицательной и не удовлетворять неравенству треугольника).
  • Более двух узлов (существование): существует зонная диаграмма конечного числа компактных и непересекающихся узлов, содержащихся внутри компактного и выпуклого подмножества пространства равномерно выпуклого . Этот результат действительно справедлив и в более общей ситуации. [3]
  • Более двух сайтов (существование и уникальность): существует уникальная диаграмма зон относительно любого набора (возможно, бесконечного) замкнутых и положительно разделенных сайтов в любом конечномерном евклидовом пространстве . Положительное разделение означает, что существует положительная нижняя граница расстояния между любыми двумя узлами. Аналогичный результат сформулирован для случая, когда нормированное пространство конечномерно и одновременно равномерно выпукло и равномерно гладко. [4]
  • неединственность : известны простые примеры даже для случая двух точечных сайтов. [2] [4]

Вычисление

[ редактировать ]

Требуется дополнительная информация.

[ редактировать ]

Помимо диаграмм Вороного , диаграммы зон тесно связаны с другими геометрическими объектами, такими как диаграммы двойных зон . [2] трисектора , [5] k-секторов , [6] диаграммы смягченных зон [7] и, как следствие, может использоваться для решения задач, связанных с движением робота и проектированием СБИС. [5] [6]

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