Аноним

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

Материал из WEGA
Строка 36: Строка 36:




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




[[Файл:PGS_1.png]]
[[Файл:PGS_1.png]]


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




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




В качестве примера нетрудно показать, что триангуляция Делоне удовлетворяет свойству a-ромба при a = ж/4. Дрисдейл и др. [ ] показали, что триангуляция с минимальным весом удовлетворяет свойству a-ромба при a = ж/4:6. Наконец, у Ли [ ] было показано, что жадная триангуляция удовлетворяет свойству a-ромба при a = л /6. Разумеется, любая триангуляция удовлетворяет свойству d-хорошего многоугольника при d = 1.
В качестве примера нетрудно показать, что триангуляция Делоне удовлетворяет свойству <math>\alpha \;</math>-ромба при <math>\alpha \;</math> = ж/4. Дрисдейл и др. [ ] показали, что триангуляция с минимальным весом удовлетворяет свойству <math>\alpha \;</math>-ромба при <math>\alpha \;</math> = ж/4:6. Наконец, у Ли [ ] было показано, что жадная триангуляция удовлетворяет свойству <math>\alpha \;</math>-ромба при <math>\alpha \;</math> = л /6. Разумеется, любая триангуляция удовлетворяет свойству d-хорошего многоугольника при d = 1.




Строка 58: Строка 58:




Теорема 5. Пусть S – множество из n точек на плоскости, 2 (0, л /2) – вещественное число, а G – триангуляция S, удовлетворяющая свойству a-ромба. Тогда G содержит подграф с максимальной степенью не выше 14 + \2ж/а], являющийся t-остовом S, где t зависит только от a. Если имеется триангуляция G, этот подграф можно построить за время O(n).
Теорема 5. Пусть S – множество из n точек на плоскости, 2 (0, л /2) – вещественное число, а G – триангуляция S, удовлетворяющая свойству <math>\alpha \;</math>-ромба. Тогда G содержит подграф с максимальной степенью не выше 14 + \2ж/а], являющийся t-остовом S, где t зависит только от a. Если имеется триангуляция G, этот подграф можно построить за время O(n).


== Применение ==
== Применение ==
4551

правка