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

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

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

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

Рассмотрим группу из $n$ разные точки $\{p_{1},\ldots ,p_{n}\}$ в евклидовой плоскости . Каждая точка называется площадкой. Когда мы говорим о диаграмме Вороного, индуцированной этими узлами, мы ассоциируем с узлом $\displaystyle {p_{k}}$ набор $\displaystyle {R_{k}}$ всех точек плоскости, расстояние которых до данного узла $\displaystyle {p_{k}}$ не больше их расстояния до любого другого места $p_{j},\,j\neq k$. Коллекция $(R_{k})_{k=1}^{n}$ Одной из этих областей является диаграмма Вороного, связанная с этими сайтами, и она вызывает разложение плоскости на области: области Вороного (ячейки Вороного).

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

$R_{k}=\{x\,|\,\,d(x,p_{k})\leq d(x,R_{j}),\,{\text{for all}}\,j\neq k\}$.

Здесь $\displaystyle {d(a,b)}$ обозначает евклидово расстояние между точками $a$ и $b$ и $d(x,A)=\inf\{d(x,a)\,|\,a\in A\}$ это расстояние между точкой $x$ и набор $A$. Кроме того, $x=(x_{1},x_{2})\in \mathbb {R} ^{2}$ так как мы рассматриваем самолет. Кортеж $(R_{k})_{k=1}^{n}$ — это диаграмма зон, связанная с сайтами.

Проблема с этим определением в том, что оно кажется замкнутым: чтобы знать $R_{k}$ мы должны знать $\displaystyle {R_{j}}$ для каждого индекса $j,\,j\neq k$ но каждый такой $\displaystyle {R_{j}}$ определяется с точки зрения $\displaystyle {R_{k}}$. Если подумать, мы видим, что на самом деле кортеж $(R_{k})_{k=1}^{n}$ является решением следующей системы уравнений:

${\begin{cases}R_{1}=\{x\in \mathbb {R} ^{2}\,|\,\,d(x,p_{1})\leq d(x,R_{j}),\,{\text{for all}}\,j\neq 1\}\\\vdots \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \vdots \\R_{n}=\{x\in \mathbb {R} ^{2}\,|\,\,d(x,p_{n})\leq d(x,R_{j}),\,{\text{for all}}\,j\neq n\}\end{cases}}$

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

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

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

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

Позволять $\displaystyle {(X,d)}$ — метрическое пространство и пусть $\displaystyle {K}$ быть набором как минимум из 2 элементов (индексов), возможно, бесконечным. Учитывая кортеж $(P_{k})_{k\in K}$ непустых подмножеств $\displaystyle {X}$, называемые сайтами, диаграмма зон относительно этого кортежа представляет собой кортеж $R=(R_{k})_{k\in K}$ подмножеств $\displaystyle {X}$ такой, что для всех $k\in K$ выполняется следующее уравнение:

$R_{k}=\{x\in X\,|\,\,d(x,P_{k})\leq d(x,R_{j}),\,{\text{for all}}\,j\neq k\}.$

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

Система уравнений, определяющая диаграмму зон, может быть представлена ​​как фиксированная точка функции, определенной в пространстве продукта. Действительно, для каждого индекса $k\in K$ позволять $\displaystyle {X_{k}}$ — множество всех непустых подмножеств $\displaystyle {X}$.Позволять

$Y=\prod _{k\in K}X_{k}$

и пусть ${\text{Dom}}:Y\to Y$ быть функцией, определяемой $\displaystyle {{\text{Dom}}(R)=S}$, где $S=(S_{k})_{k\in K}$ и

$S_{k}=\{x\in X\,|\,\,d(x,P_{k})\leq d(x,R_{j}),\,{\text{for all}}\,j\neq k\}.$

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

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

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

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

Вычисление

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

Связанные объекты и возможные применения

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