Научная литература
booksshare.net -> Добавить материал -> Математика -> Препарата Ф. -> "Вычислительная геометрия: Введение" -> 62

Вычислительная геометрия: Введение - Препарата Ф.

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 56 57 58 59 60 61 < 62 > 63 64 65 66 67 68 .. 180 >> Следующая


Адекватное описание текущего политопа Р дает его граф граней Н(Р) (т.е. диаграмма Хассе для множества граней политопа Р, основанная на отношении включения; см. разд. 3.1), из которого удален узел, соответствующий политопу Р в целом, так как он является избыточным при размерности Р, равной d. В качестве структуры данных можно было бы использовать

CH(f3Up) случай (Z) (а)

any чай (7)|

CU(fg\Jp) случай (Z)(b)

3.4. Выпуклые оболочки размерности большей двух

169

(d + 1) списков L_i, L0, L\, . . . , La-i, где L/— список /-граней. Каждая запись в относится к некоторой /-грани / и содержит:

(1) аффинный базис БАЗИС (/) грани /;

(2) указатели СУПЕРГРАНЬ(/) на каждую (/+1)-грань, содержащую /, и указатели ПОДГРАНЬ(/) на каждую (/—1)-грань, содержащуюся в f;

(3) указатели ГИПЕРГРАНЬ (/) на каждую гипергрань, содержащую f.

Указатели (3) играют основную роль при определении относительного положения точки (п. (а) случая (2) теоремы 3.15). Остальные данные нужны для получения необходимой информации о том, следует ли повышать размерность грани, чтобы в конечном итоге превратить ее в гипергрань.

Изменение политопа Р, вызванное добавлением новой точки, можно осуществить не единственным способом. Хотя предлагаемый ниже подход допускает некоторые улучшения на уровне алгоритма, зато он довольно прост для описания.

Пусть политоп Р представлен своим графом граней Н(Р). Создадим другой граф НР(Р), изоморфный Н(Р), узлы которого определяются следующим образом:

{/'•/' = СН(/ U р) для каждой грани / политопа Р),

и, кроме того, для каждой грани / политопа Р создадим ребро, отображающее включение f cz f (рис. 3.28(b)). Все, что требуется сделать при создании f, это добавить к БАЗИС (/) точку р так как по предположению точки находятся в общем положении (что гарантирует выполнение условия p^aff(f)). Обозначим полученный таким образом граф Н(Р, р).

Очевидно, что НР(Р) содержит опорный «конус» к Р из точки р. Действительно, когда размерность политопа Р меньше d, то НР(Р) представляет в точности опорный конус, и изменение текущего политопа на этом заканчивается с Н(Р, р) = = Я(СН(Р U />)).

Рассмотрим механизм корректировки в случае, когда размерность политопа Р равна d. В предположении, что точка р лежит вне Р, требуемый граф H(CH(P\jp)) получается из Н(Р,р) в результате удаления некоторых узлов графа. А именно имеет место следующее:

(1) Н(Р) строго содержит часть, затеняемую конусом. В самом деле, каждая грань f политопа Р такая, что для каждой гиперграни F, содержащей f, точка р находится над F, принадлежит тени и поэтому должна быть удалена (в примере на рис. 3.28 это имеет место для р3, е34 и е2з). Воспользуемся следующим очевидным свойством:

170

Гл. 3. Выпуклые оболочки: основные алгоритмы

Свойство 1. Если f<?CH(R\Jp) и f cz то \' ф СН(Р U р).

Использование свойства 1 позволяет удалить в графе Я(Р, р) все узлы, доминирующие над f. (Грани, удаляемые по этой причине, показаны на рис. 3.28(c) черными кружками.) Для каждой удаляемой грани / удаляются также инцидентные ей ребра (т. е. как СУПЕРГРАНЬ (/), так и ПОДГРАНЬ (f)).

(2) НР(Р) содержит опорный конус. В самом деле, каждая грань f политопа Р такая, что для каждой гиперграни F, содер-

3.4. Выпуклые оболочки размерности большей двух

171

жащей f, точка р находится под F, также является гранью CH(PUp) (случай (1) теоремы 3.15), так что СН(/1)р)е= е НР(Р) должна быть удалена (в нашем примере это верно для f = р\, ец, е12). Воспользуемся следующим очевидным свойством:

Свойство 2. Если СН(/ U р)Ф СН(Р U р) и /с/', то CH(/'U р)фСЩР\)р).

Использование свойства 2 позволяет удалять в графе НР(Р) все узлы, доминирующие над СН(/ U р). (Грани, удаляемые по этой причине, показаны на рис. 3.28(c) заштрихованными кружками.) Затем для каждого узла графа НР(Р), удаленного таким образом, удаляются инцидентные ему ребра. Этот результирующий граф, полученный путем удаления из Н(Р, р) некоторых узлов, является графом граней политопа CH(PUp). Заметим также, что, когда точка р не является внешней по отношению к Р, свойство 2 остается справедливым для каждой грани f политопа Р. Так что в этом случае удаляется целиком подграф НР(Р) и при этом получается правильный результат СН(Р U р) = СН(Р).

С точки зрения реализации основной частью этого метода является процедура классификации каждой из N вершин политопа Р относительно точки р. При этом вершина может быть классифицирована как вогнутая, выпуклая или опорная (в соответствии с обобщением терминологии из разд. 3.3.6). В частности,

(вогнутой, если для каждой гиперграни F, содержащей v, точка р находится вершина v отно- под р. сительно точки р\ ' „

является выпуклой, если для каждой гиперграни

F, содержащей v, точка р находится над F; ' опорной во всех других случаях.

В качестве интересного упражнения читателю предлагается самому придумать метод, выполняющий указанную выше классификацию вершин за время О (cpd-i) + О (Nd), где, как обычно, (pd_i — число гиперграней политопа Р (упражнение 3.9 в конце главы). Если такая классификация сделана, то свойство 1 применимо ко всем граням, доминирующим над любой из выпуклых вершин, а свойство 2 — ко всем граням, доминирующим над вогнутыми вершинами в ЯР(Р), и эта операция может быть выполнена за время, пропорциональное полному числу вершин и ребер Н(Р). Нетрудно показать, что последняя величина равна 0(<Pd-i). Таким образом, полное время одной операции корректировки выпуклой оболочки равно 0(q>d-i), а так как выполняется N таких операций, то получаем следующую теорему:
Предыдущая << 1 .. 56 57 58 59 60 61 < 62 > 63 64 65 66 67 68 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed