Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Напомним, что для симплициального ^-политопа каждая его гипергрань, являющаяся (d—1)-симплексом, определяется в точности d вершинами. Кроме того, справедлива теорема, непосредственно следующая из сказанного.
Теорема 3.13. В симплициальном политопе некоторая под-грань является общей в точности для двух гиперграней и две гиперграни F\ и F2 имеют общую подгрань е тогда и только тогда, когда е определяется общим подмножеством из (d—1) вершины для множеств вершин, определяемых F{ и F2 (в этом случае F\ и F2 называются смежными по е).
Эта теорема служит основой для рассматриваемого метода, который использует некоторую подгрань е уже построенной гиперграни F\ для построения смежной с ней гиперграни F2, имеющей с Fi общую подгрань е. В этом смысле подграни являются основными геометрическими объектами рассматриваемого метода ').
Пусть 5 = {pi, р2, . . . , ри} — конечное множество точек в Еа и предположим, что известна некоторая гипергрань F выпуклой оболочки CH(S) вместе со всеми своими подгранями. Механизм перехода от гиперграни F к смежной с ней гиперграни F', имеющей с F общую подгрань е, заключается в определении среди всех точек множества S, не являющихся вершинами F, такой точки р', что все другие точки находятся под гиперплоскостью aff(e U р'). Другими словами, среди всех гиперплоскостей, опре-
') В самом деле, характеристика метода «заворачивания подарка» как «ориентированного на ребре» означает в нашей терминологии «ориентированный на подграни».
162 Гл. 3. Выпуклые оболочки: основные алгоритмы
деляемых е и некоторой точкой из 5, не принадлежащей F, ищется гиперплоскость, образующая «наибольший угол» (в некотором смысле) с aff (F). Для случая d = 3 эта ситуация показана на рис. 3.25(a). Здесь просматривается совокупность полуплоскостей, имеющих общую прямую, проходящую по ребру е, и среди них ищется полуплоскость, образующая наибольший угол <я {выпуклый угол) с полуплоскостью, содержащей F. На рис. 3.25(a) искомая полуплоскость содержит точку р&.
(а) (Ь)
Рис. 3.25. (а) — Иллюстрация выбора полуплоскости, определяемой ребром е и точкой р6 и образующей наибольший выпуклый угол с полуплоскостью, содержащей F; (Ь) — иллюстрация вычисления котангенса угла.
Сравнение углов производится через сравнение котангенсов этих углов. Пусть п — единичная нормаль к F (в полупространстве под aff(jF)), а а — единичный вектор, ортогональный как ребру е, так и вектору п (таким образом, ориентация вектора а аналогична ориентации вектора nXP2pi). Обозначим через v* вектор p2pk. Котангенс угла, образованного гиперплоскостью, содержащей F, с гиперплоскостью, содержащей е и pk, задается отношением \Up2\/\~UV\, где | Up2\ = vs-a7- и | UV\ = vknT. Таким образом, для каждой точки ри, не принадлежащей F, вычисляется значение
Р*Д -vk-a.T/vk-nT (3.10)
и выбирается такое р«, что
p(- = maxpft. (3.11)
В случае, когда результирующий политоп является симплици-альным, последнее уравнение имеет единственное решение.
3.4. Выпуклые оболочки размерности большей двух
163
Представив наглядным образом ситуацию в привычном для нас трехмерном пространстве, легко показать, что в пространстве произвольной размерности d соотношения (3.10) и (3.11) дают решение нашей задачи. Вычислительную сложность этой примитивной операции можно легко оценить. Предположим, что вектор п известен (это единичная нормаль к aff(/7)), и будем считать, что подгрань е определяется вершинами {р[, р'2, ...
р'а_{}. Следовательно, вектор а ортогонален вектору п и каждому из (d — 2) векторов p\p'd_y и может быть определен в результате решения системы из (d — 2) уравнений с (d—1) неизвестными с последующим нормированием результата, чтобы получить вектор единичной длины. Эта процедура включает 0(d3) арифметических операций. Для вычисления каждого требуется 0(d) арифметических операций, а выбор р,- осуществляется за О (Nd) операций. Теперь можно построить единичную нормаль к новой гиперграни F'. Эта нормаль пропорциональна вектору —р,а + п. Таким образом, полная сложность процедуры перехода от гиперграни F к смежной с ней гиперграни F' (шаг «заворачивания подарка») равна 0(dz) + 0(Nd).
Поняв механизм основной операции «заворачивания подарка», можно описать организацию всего алгоритма в целом. Алгоритм начинает свою работу с некоторой исходной гиперграни (далее мы увидим, как найти ее) и для каждой ее подграни строит смежную гипергрань. Затем он переходит к новой гиперграни и продолжает подобную обработку до тех пор, пока не будут построены все гиперграни. Для каждой вновь полученной гиперграни строятся все ее подграни и при этом поддерживается список всех подграней, являющихся кандидатами на использование на шаге «заворачивания подарка». (Отметим, что некоторая подгрань е, общая для гиперграней F и F', может рассматриваться в качестве такого кандидата лишь в случае, когда либо F, либо F', но не обе одновременно была построена в процессе «заворачивания подарка».) Упорядоченный обход всех гиперграней лучше всего организовать, использовав обычную очередь гиперграней Q и файл 0~, содержащий подграни.
