Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Пока у нас нет причин заранее сомневаться в том, что свойство выпуклости поможет нам в решении задачи. Стоит продолжить исследование в этом направлении, прежде чем отказываться от этой идеи. По крайней мере следует рассмотреть несколько иные подходы к определению диаметра. Один из них дает следующая теорема.
Теорема 4.18. Диаметр выпуклой фигуры равен наибольшему из расстояний между двумя параллельными опорными прямыми к этой фигуре [Yaglom, Boltyanski (1961)].
На примере рис. 4.20 видно, что параллельные прямые можно провести не через каждую пару точек. Например, никакие
4.2. Приложения в статистике
219
две опорные прямые, проходящие соответственно через вершины ?>4 и рв, не являются параллельными. Это значит, что отрезок pipe не является диаметром. Пдра-точек, через которые можно провести параллельные опорные прямые, называется противолежащей парой. В силу теоремы 4.18 необходимо рассматривать лишь противолежащие пары точек. Задача заключается в том, чтобы определить противолежащие пары, не перебирая все возможные пары точек.
Рассмотрим вершину р, выпуклого многоугольника Р, вершины которого занумерованы в порядке обхода против часовой
Ps Ри
Pi
Рис. 4.20. Не все пары вершин являются противолежащими. Через вершины р4 и р6 нельзя провести параллельные опорные прямые. Таким образом, р4Рб не может быть диаметром.
стрелки (рис. 4.21(a)). Предположим, что мы двигаемся по граниие^шдщ^голъш^ Р против часовой стрелки. Начав движе-нИ€~в~Тзе^ш1ине pi, будем двигаться до тех пор, пока не достигнем вершины q^\ максимально удаленной от рг-ip;1). В случае неоднозначности выбора, т. е. когда Р содержит параллельные ребра, q{? — это первая вершина с заданным свойством, встретившаяся при обходе. Аналогичным образом определяется вершина q{[\ максимально удаленная от ptpi+i, которая выявляется при обходе границы многоугольника Р по часовой стрелке, начиная с вершины pi. Утверждается, что цепь вершин между qW и qW (включая эти вершины) дает множество С(р,), каждая вершина которого образует с р, противолежащую пару2). Действительно, пусть <а,- -:::~внешний угол, образуемый p;-ip; и p,p,+i (а,->я). Ясно, что (pi, ps) является противолежащей
') Точнее сказать, ищется вершина, максимально удаленная от прямой, содержащей отрезок pi-\Pi. — Прим. перев.
2) Вершины qty и а^ разбивают границу Р на две цепи. К С (pi) относятся вершины той из них, которая не содержит вершину pi. — Прим. перев.
220
Гл. 4. Выпуклые оболочки: расширения и приложения
парой тогда и только тогда, когда существует прямая, попадающая в пересечение углов as и а; (рис. 4.21(b)). Так как С(р<) — это выпуклая цепь, то каждая вершина pseC(p,) обладает этим свойством. Более того, для каждой вершины Р, не принадлежащей C(pi), справедливо противоположное высказывание.
(Ъ)
Рис. 4.21. Характеризация противолежащих пар. Пересечение углов а,- и as представляет собой два клина с совпадающими вершинами.
Это свойство немедленно подсказывает алгоритм порождения всех противолежащих пар. Основная операция, необходимая для этого, заключается в проверке условия максимальной удаленности точки от прямой, определяемой отрезком p<p;+i. Это легко сделать, вычислив площадь (с учетом знака) треугольника (р,-, Pi+i, р) (см. разд. 2.2.1). Теперь можно описать простой алгоритм. В этом алгоритме предполагается, что вершины многоугольника Р, составляющие при обходе против часовой стрелки последовательность (рь р2, ..., ры) (в которой за рц следует pi), представлена списком с указателем СЛЕ-ДУЮЩИЙ[ ], дающим следующий элемент списка.
4.2. Приложения в статистике
221
procedure ПРОТИВОЛЕЖАЩИЕ-ПАРЫ
1. begin p:=pN\
2. <7:= СЛЕДУЮЩИЙ^];
3. while (Площадь(р, СЛЕДУЮЩИИ[р],
СЛЕДУЮЩИЙ!?]) > Площадь
(р, СЛЕДУЮЩИЙ^],?)) do
q:= СЛЕДУЮЩИЙ^]; (* продвигаться по границе Р до тех пор, пока не будет достигнута вершина, максимально удаленная от р СЛЕДУЮЩИЙ[р] *)
4. qo-=q;
5. while (q Ф р0) do
6. begin р:= СЛЕДУЮЩИЙ[р];
7. печать (p,q);
8. чуЫ1е(Площадь(р,СЛЕДУЮЩИИ[р],
СЛЕДУЮЩИЙ^])) > Площадь(р,СЛЕДУЮЩИЙ[р],</)) do
9. begin q := СЛЕДУЮЩИЙ!?];
10. ii{(p,q) ф (q0,p0)) then печать(р,<7) end;
11. if (Площадь(р, СЛЕДУЮЩИЙ^],
СЛЕДУЮЩИЙ[<7])) = ПЛ ОЩАДЬ(р, СЛЕДУ ЮЩИЙ[р], д)) then
12. \i(p,q) Ф (q0,pN)) thtn печать(р, СЛЕДУ ЮЩИЙЫ)
(* обработка параллельных ребер *)
end
end.
Рис. 4.22 иллюстрирует работу приведенного выше алгоритма.
Строки 1—3 алгоритма описывают поиск вершины q^\ если использовать обозначения, введенные ранее (в алгоритме эта вершина обозначена q0). Последующий цикл while, в котором формируется множество С (pi), использует два указателя р н q. Эти два указателя двигаются по границе многоугольника Р в направлении против часовой стрелки, при этом р продвигается от pN до a q — от q^ до pN. Противолежащая пара порождается каждый раз, когда либо происходит продвижение любого из двух упомянутых указателей (строки 5—7 и 9—10), либо встречается пара параллельных ребер многоугольника Р (строки 11—12). Очевидно, что первой порожденной парой будет (р, q)= (ро, q0) (при первом выполнении строки 7). Утверждается, что последней парой будет (р, q) = (qo, Pn), так как Pn — это последнее значение, принимаемое q (иначе основной цикл while в строке 5 завершается). Таким образом, каждая про-
