Параллельное программирование



              

Основные предположения - часть 2


Отсюда следует, что геометрически мы можем продемонстрировать верность гипотезы в двух- и трехмерном пространстве. В общем же случае доказательство ее справедливости должно быть аналитическим.

Итак, поясним высказанное предположение "плоским" рис. 6.4.

Соотношение углов между нормалями смежных граней

Рис. 6.4.  Соотношение углов между нормалями смежных граней

Выделим произвольную вершину A многогранника R. Она "окружена" образующими ее гранями (на плоскости — ребрами). Пусть pj — одна из них. Любая грань, не являющаяся образующей вершины A, например — грань (ребро) pq, добавляет угол излома поверхности в угол наклона ? ее нормали Nq. Точка пересечения pj и pq находится вне R. Тогда должна существовать образующая эту же вершину грань (ребро) pl, нормаль к которой Nl имеет меньший угол наклона, ? <

.

Представим (рис. 6.5) аналогичную картину в трехмерном пространстве.

Соотношение углов между нормалями в трёхмерном пространстве

Рис. 6.5.  Соотношение углов между нормалями в трёхмерном пространстве

Пусть p2 и p3 не являются смежными на данной поверхности многогранника R, то есть не имеют общего ребра и, следовательно, совместно не являются образующими какой-либо вершины. Тогда существует одна или более разделяющих их граней, здесь, например — грань p1, нормаль к которой N1 образует с нормалью N2 угол ? меньший угла

— угла между нормалями N2 и N3.

Минуя формальное и строгое доказательство, продолжим пояснение гипотезы на качественном уровне.

Грани p1 и p2 являются образующими двух вершин A и B. Для гарантии смежности этих граней, то есть того, что они совместно являются образующими какой-то вершины, можно в основу выбора такой вершины положить минимальный угол между нормалями к ним. То есть будем считать, что если для фиксированной грани pj найден минимальный из углов между нормалью Nj к этой грани и нормалями ко всем другим граням этой же поверхности, — угол между нормалью Nj и нормалью Nl, то две грани pj и pl совместно являются образующими хотя бы одной вершины этой поверхности.

Чтобы найти третью грань — третье уравнение для нахождения точки в трехмерном пространстве, следует искать такую грань (например, p4 на рис. 6.5), между нормалью к которой и нормалями N1 и N2 углы также меньше тех углов, которые N1 и N2 образуют с нормалями несмежных граней.Такая грань будет смежной и p1, и p2.

Теорема. Пусть p — произвольная грань верхней (нижней) поверхности многогранника R допустимых решений задачи ЛП. Составим неубывающую последовательность углов между нормалью к этой грани и нормалями всех граней этой же поверхности (включая нормаль к этой же грани; этот угол равен нулю). Первые n минимальных отличных от нуля углов этой последовательности указывают на n граней, являющихся образующими некоторой вершины многогранника R.

Доказательство. Пусть среди выделенных таким образом граней есть грань, не являющаяся совместно с другими образующей одной вершины. Тогда, по теореме-гипотезе, существует образующая ту же вершину грань, не параллельная первой и такая, нормаль к которой составляет с нормалью к p угол, меньший, чем выделенный по указанной последовательности. Это противоречит правилу выбора n минимальных углов.




Содержание  Назад  Вперед