4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 41: | Строка 41: | ||
[[Файл:PGS_1.png]] | [[Файл:PGS_1.png]] | ||
С левой стороны изображено свойство <math>\alpha \;</math>-ромба. По меньшей мере один из треугольников <math>\Delta_1 \;</math> и <math>\Delta_2 \;</math> не содержит внутри точек множества 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. Пусть <math>\alpha \in (0, \pi / a) \;</math> и <math>d \ge 1 \;</math> – вещественные числа, а G – плоский граф, удовлетворяющий свойствам <math>\alpha \;</math>-ромба и d-хорошего многоугольника. В таком случае граф G является t-остовом для множества вершин G, где t = | '''Теорема 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>.''' | ||
В качестве примера нетрудно показать, что триангуляция Делоне удовлетворяет свойству <math>\alpha \;</math>-ромба при <math>\alpha \;</math> | В качестве примера нетрудно показать, что триангуляция Делоне удовлетворяет свойству <math>\alpha \;</math>-ромба при <math>\alpha = \pi/4 \;</math>. Дрисдейл и др. [11] показали, что триангуляция с минимальным весом удовлетворяет свойству <math>\alpha \;</math>-ромба при <math>\alpha = \pi / 4,6 \;</math>. Наконец, у Ли [13] было показано, что жадная триангуляция удовлетворяет свойству <math>\alpha \;</math>-ромба при <math>\alpha = \pi / 6 \;</math>. Разумеется, любая триангуляция удовлетворяет свойству d-хорошего многоугольника при d = 1. | ||
Строка 53: | Строка 53: | ||
Теорема 4. Пусть S – множество n точек на плоскости. Триангуляция Делоне для множества S содержит подграф с максимальной степенью не выше 17, являющийся t-остовом S для некоторого константного t. Если имеется триангуляция Делоне, этот подграф можно построить за время O(n). | '''Теорема 4. Пусть S – множество n точек на плоскости. Триангуляция Делоне для множества S содержит подграф с максимальной степенью не выше 17, являющийся t-остовом S для некоторого константного t. Если имеется триангуляция Делоне, этот подграф можно построить за время O(n).''' | ||
На самом деле результат оказался даже более общим: | На самом деле результат оказался даже более общим: | ||
Теорема 5. Пусть S – множество из n точек на плоскости, | '''Теорема 5. Пусть S – множество из n точек на плоскости, <math>\alpha \in (0, \pi / 2) \;</math> – вещественное число, а G – триангуляция S, удовлетворяющая свойству <math>\alpha \;</math>-ромба. Тогда G содержит подграф с максимальной степенью не выше <math>14 + \left \lceil 2 \pi / \alpha \right \rceil</math>, являющийся t-остовом S, где t зависит только от a. Если имеется триангуляция G, этот подграф можно построить за время O(n).''' | ||
== Применение == | == Применение == |
правка