Планарные геометрические остовы: различия между версиями

Пусть S – множество точек на плоскости, а G – неориентированный граф с множеством вершин S, каждое ребро (u, v) которого имеет вес, равный евклидовому расстоянию |uv| между точками u и v. Для любых двух точек p и q в S обозначим кратчайший путь между ними в графе G за <math>\delta_G (p, q) \;</math>. Если <math>t \ge 1 \;</math> – вещественное число, то Gis является ''t-остовом'' S в случае, если <math>\delta_G(p, q) \le t |pq| \;</math> для любых двух точек p и q в S. Таким образом, если значение t близко к 1, то граф G содержит достаточно хорошие приближения <math>\tbinom{n}{2}</math> евклидовых расстояний, определяемых парами точек в S. Если к тому же G включает O(n) ребер, то этот граф можно считать разреженным приближением полного графа на S. Наименьшее значение f, при котором G будет являться t-остовом, называется ''коэффициентом растяжения'' (или ''протяженностью'') G. Исчерпывающий обзор геометрических остовов можно найти в работе Нарасимхана и Смида [16].

Предположим, что каждое ребро (u, v) графа G реализовано в видео отрезка прямой, соединяющей точки u и v. Граф G называется [[планарный граф|планарным]], если его ребра пересекаются только в точках их общих вершин.

Задача 1. Определить наименьшее вещественное число t > 1, для которого выполняется следующее утверждение: Для каждого множества S из n точек на плоскости существует плоский граф с множеством вершин S, являющийся t-остовом для S. Разработать эффективный алгоритм построения такого плоского t-остова.

Задача 2. Определить наименьшее целое положительное число D, для которого выполняется следующее утверждение: Существует константное значение t, такое, что для каждого множества S из n точек на плоскости существует плоский граф с множеством вершин S и максимальной степенью, не превышающей D, который является t-остовом для S. Разработать эффективный алгоритм построения такого плоского t-остова.

Пусть S – конечном множество точек на плоскости, имеющих общее положение; т.е. никакие три точки из S не лежат на одной прямой и никакие четыре – на одной окружности. [[Плоская_триангуляция|Триангуляцией]] Делоне для множества S является плоский граф с множеством вершин S, в котором (u, v) является ребром в том и только том случае, если существует окружность, проходящая через u и v, внутри которой не содержится ни одной точки S. (Поскольку точки S находятся в общем положении, этот гарф представляет собой триангуляцию). Триангуляция Делоне на множестве из n точек на плоскости может быть построена за время O(n log n). Добкин, Фридман и Суповит [10] первыми показали, что коэффициент растяжения триангуляции Делоне ограничен константой. Они доказали, что триангуляция Делоне является t-остовом для <math>t = \pi (1 + \sqrt{5})/2 \;</math>. Наилучшую известную на данный момент верхнюю границу коэффициента растяжения для этого графа предложили Кил и Гутвин [12]:

Несколько более строгий результат был доказан Бозе и др. [3]. Они доказали, что для любых двух точек p и q из S триангуляция Делоне содержит путь между p и q, длина которого не превышает <math>t = 4 \pi \sqrt{3} / 9 \; |pq|</math>, а длина каждого ребра на этом пути не превышает |pq|.

Левкопулос и Лингас [14] обобщили результат теоремы 1: Предположим, что дана триангуляция Делоне для множества S. Тогда для любого вещественного числа r > 0 за время O(n) можно построить плоский граф G с множеством вершин S, являющийся t-остовом для S, где <math>t = (1 + 1/r) 4 \pi \sqrt{3}/9</math>, совокупная длина ребер которого будет не более чем в 2r + 1 раз превышать вес остовного дерева для S.

'''Теорема 2. Пусть S – конечное множество точек на плоскости. Рассмотрим триангуляцию Делоне для S, основанную на выпуклой функции расстояния, определяемой при помощи равностороннего треугольника. Этот плоский граф является 2-остовом для S (в котором длины путей измеряются при помощи евклидовой метрики).'''

Дас и Джозеф [9] следующим образом обобщили утверждение теоремы 1 (см. рисунок). Пусть G – плоский граф с множеством вершин S, а <math>\alpha \;</math> – вещественное число, <math>0 < \alpha < \pi/2 \;</math>. Для любого ребра e графа G обозначим за <math>\Delta_1 \;</math> и <math>\Delta_2 \;</math> два равнобедренных треугольника с основанием e и углом при основании <math>\alpha \;</math>. Ребро e удовлетворяет ''свойству <math>\alpha \;</math>-ромба'', если по меньшей мере один из треугольников <math>\Delta_1 \;</math> и <math>\Delta_2 \;</math> не содержит внутри точек множества S. Плоский граф G удовлетворяет свойству <math>\alpha \;</math>-ромба, если каждое ребро e графа G удовлетворяет этому свойству. Для вещественного числа <math>d \ge 1 \;</math> граф G удовлетворяет свойству d-хорошего многоугольника, если для каждой грани f графа G и для каждых двух вершин p и q на границе f, таких, что соединяющий их отрезок прямой полностью находится в f, длина пути между p и q вдоль границы f не превышает d|pq|. Дас и Джозеф [9] доказали, что любой плоский граф, удовлетворяющий одновременно свойству <math>\alpha \;</math>-ромба и свойству d-хорошего многоугольника, является t-остовом для некоторого вещественного числа t, которое зависит только от <math>\alpha \;</math> и d. Значение t было несколько улучшено Ли [13]:

''С левой стороны изображено свойство <math>\alpha \;</math>-ромба. По меньшей мере один из треугольников <math>\Delta_1 \;</math> и <math>\Delta_2 \;</math> не содержит внутри точек множества S. Справа проиллюстрировано свойство d-хорошего многоугольника. p и q – две вершины на одной и той же грани f, которые видят друг друга. По меньшей мере один из двух путей между p и q вдоль границы f имеет длину, не превышающую d|pq|''

'''Теорема 3. Пусть <math>\alpha \in (0, \pi / a) \;</math> и <math>d \ge 1 \;</math> – вещественные числа, а G – плоский граф, удовлетворяющий свойствам <math>\alpha \;</math>-ромба и d-хорошего многоугольника. В таком случае граф G является t-остовом для множества вершин G, где <math>t = \frac{8 (\pi - \alpha)^2 \; d}{\alpha^2 \; sin^2 (\alpha / 4)}</math>.'''

Теперь рассмотрим задачу 2, касающуюся построения плоских остовов с невысокой максимальной степенью. Первый результат для этой задачи был получен Бозе и др. [2]. Они доказали, что триангуляция Делоне любого конечного множества точек содержит подграф с максимальной степенью не выше 27, являющийся t-остовом (для некоторого константного t). Ли и Ван [15] улучшили этот результат, показав, что триангуляция Делоне содержит t-остов со степенями не более 23. Если имеется триангуляция Делоне, подграфы в [2, 15] можно построить за время O(n). Лучший известный на сегодня результат для задачи 2 дали Бозе и др. [6]:

Плоские остовы применяются при решении задач поиска путей и маршрутизации в режиме онлайн, которые возникают, например, в географических информационных системах и сетях коммуникаций. В этих областях применения, как правило, среда в целом неизвестна, и маршрутизацию приходится осуществлять, зная только местонахождение источника, точку назначения и ближайших соседей текущей позиции. Бозе и Морин [4, 5] показали, что в рамках этой модели имеются эффективные стратегии маршрутизации для планарных графов, такие как триангуляция Делоне и графы, одновременно удовлетворяющие свойствам a-ромба и d-хорошего многоугольника. Эти стратегии являются конкурентными в том смысле, что длины рассчитанных путей не превышают произведения евклидова расстояния между источником и получателем на константный коэффициент. Кроме того, эти стратегии маршрутизации требуют ограниченного количества памяти.

1. Определить наименьшее вещественное число t, при котором триангуляция Делоне любого конечного множества точек на плоскости является t-остовом. Распространено мнение, что t = л /2. Согласно теореме 1, t < 4JT^3/9.

2. Определить наименьшее вещественное число t, при котором для любого конечного множества точек на плоскости существует плоский t-остов. Согласно теореме 2, t < 2. Если взять частный случай S в виде множества из четырех вершин квадрата, получается, что t должно быть не меньше p2.

3. Определить наименьшее целое число D, при котором триангуляция Делоне любого конечного множества точек на плоскости содержит t-остов (для некоторого константного значения t), максимальная степень которого не превышает D. Согласно теореме 4, D < 17. Из результатов, полученных Ароновым и др. [ ], следует, что значение D должно быть не менее .

4. Определить наименьшее вещественное число D, при котором для любого конечного множества точек на плоскости существует плоский t-остов (для некоторого константного значения t), максимальная степень которого не превышает D. Согласно теореме 4 и данным работы [ ], 3 < D < 17.