Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
222 Гл. 4. Выпуклые оболочки: расширения и приложения
тиволежащая пара порождается лишь один раз. И так как при выполнении цикла while указатель р продвигается от р0 до q0,
а указатель q — от q0 до ры, то произойдет всего N продвижений,
1
2
Р;
3
р
3
рз
3
3
Ps
3
~ро
'б
'Ро рь!
р.
6
'Р; Р5'
7
9
'Pi Рб>
10
С Р1 Р?1
12
р2
б
'Р2 Р6>
7
Р7
9
'Р2 Р7'
10
Р8
'Рг Ре1
10
Рэ
9
(р2 р9)
10
р3
6
(Р3 Рэ1
7
р4
6
' Р4 Рэ'
7
р.
6
<Р5 Рэ»
7
Рис. 4.22. Иллюстрация работы процедуры ПРОТИВОЛЕЖАЩИЕ-ПАРЫ. Обратите внимание на то, что ребра р,р2 и р6р7 параллельны.
и, следовательно, при отсутствии параллельных ребер будет порождено N противолежащих пар. Если имеются пары параллельных ребер, то их число не может превышать LN/2J, и, следовательно, полное число противолежащих пар, порождаемых алгоритмом, не превосходит 3/V/2.
Алгоритм можно изменить таким образом, что он будет выдавать лишь такие противолежащие пары (их в точности N), которые являются кандидатами на место диаметра. Действительно, каждый раз, когда два ребра многоугольника парал-
4.3. Замечания и комментарии
223
лельны, необходимо рассматривать лишь диагонали определяемой ими трапеции.
Так как для определения диаметра многоугольника вполне достаточно знать все его противолежащие пары (согласно теореме 4.18), то имеет место следующий результат.
Теорема 4.19. Диаметр выпуклого многоугольника может быть найден за линейное по числу его вершин время.
Следствие 4.1. Диаметр множества из N точек на плоскости может быть найден за оптимальное время 8 (N log N).
Теорема 4.20. Диаметр множества из N точек, выбранных из Np-распределения на плоскости (см. разд. 4.1.1), может быть найден в среднем за время О (N).
Доказательство. Согласно теореме 4.5, выпуклую оболочку можно найти в среднем за линейное время. Применяя теорему 4.12, получаем необходимый результат.
Теорема 4.19 в сочетании с теоремой 4.12 (см. разд. 4.1.4) позволяют получить следующий интересный результат.
Следствие 4.2. Диаметр простого многоугольника может быть найден за линейное время.
На первый взгляд может показаться, что при прохождении всех противолежащих пар для определения диаметра выполняется лишняя работа. Легко убедиться, что при отсутствии параллельных ребер этого не происходит. Ключевым в этом вопросе является понятие диаметральной пары вершин в многоугольнике Р, т. е. такой пары вершин в многоугольнике Р, расстояние между которыми в точности равно диаметру множества вершин. Так как диаметральная пара является также противолежащей парой, то в множестве вершин имеется не более N диаметральных пар. Классический результат, полученный Эр-дёшем [Erdos (1964)], состоит в следующем:
Теорема 4.21. В множестве из N точек на плоскости может быть не более N пар точек, на которых достигается максимальное расстояние между точками множества.
Очевидно, что данная оценка достигается на правильных /V-угольниках (N^3, нечетное).
4.3. Замечания и комментарии
Оптимальное решение задачи вычисления диаметра множества точек на плоскости было получено методом, обсуждавшимся в разд. 4.2.3. Довольно соблазнительно расширить этот подход на пространства более высокой размерности. В слу-
224 Г л. 4. Выпуклые оболочки: расширения и приложения
чае пространства Е3 еще одним фактором, стимулирующим интерес к этому вопросу, является следующий результат [Grunbaum (1956)] (известный как гипотеза Васони):
Теорема 4.22. В множестве из N точек в трехмерном пространстве число пар точек, на которых достигается максимальное расстояние, не превышает 2N — 2.
К сожалению, большое сходство теорем 4.21 и 4.22 скрывает тот факт, что, в то время как в случае плоскости число диаметральных пар и число противолежащих пар растут как 0(N), в трехмерном пространстве для них имеют место оценки 0(N)
ждения всех противолежащих пар требует времени О (N2) и, возможно, является более трудоемкой по сравнению с методом «грубой силы», основанным на вычислении расстояния между каждой парой точек. Хотя диаметральные пары составляют подмножество противолежащих пар, до сих пор не найден эффективный способ выделения таких пар. Несмотря на ее внешнюю простоту, задача вычисления диаметра множества точек в трехмерном пространстве явилась для многих исследователей преградой, о которую разбивались все их усилия.
В d-мерном пространстве диаметр множества из N точек всегда можно определить за время 0(dN2), вычисляя расстояние между каждой парой точек.
Следующая теорема сужает круг возможностей сделать это более эффективно:
Теорема 4.23 [Erdos (I960)]. В множестве из N точек в d-мерном (d > 3) пространстве число пар точек, на которых достигается максимальное расстояние, может достигать N2/(2— \_d/2 J )+ 0(N2-E), где e > 0 — некоторое число.
