11.4. Выпуклые многогранники и выпуклые оболочки.

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

Рис. 11.18

Рис. 11.19

Рис. 11.20

в некотором смысле наименьшим выпуклым множеством, содержащим F (рис. 11.18). А точное определение его таково.

Выпуклой оболочкой множества F называется пересечение всех выпуклых множеств, содержащих F (рис. 11.19). Оно обозначается

Поскольку пересечение выпуклых множеств есть выпуклое множество, то выпуклая оболочка множества является выпуклым множеством.

Выпуклая оболочка выпуклой фигуры есть, очевидно, сама эта фигура. Нас будут интересовать выпуклые оболочки конечного числа точек. Очевидно, выпуклой оболочкой одной точки является сама эта точка.

Выпуклой оболочкой двух точек является отрезок (рис. 11.20а). Действительно, отрезок является выпуклым множеством, содержащим точки . С другой стороны, любое выпуклое множество, содержащее содержит и отрезок . Поэтому

Ясно, что выпуклой оболочкой любой системы S конечного числа точек лежащих на одной прямой (рис. 11.20 б), является отрезок, соединяющий наиболее удаленные точки из этой системы

Рис. 11.21

Рассмотрим систему. S, состоящую из трех точек не лежащих на одной прямой. Чтобы получить выпуклую оболочку этих трех точек, следует точку соединять со всеми точками отрезка (рис. 11.21). В результате получим треугольник , который и является выпуклой оболочкой точек

Добавим к трем точкам еще одну точку и будем искать выпуклую оболочку системы из четырех точек

Возможны такие случаи.

1) Точка принадлежит треугольнику . Ясно, что тогда (рис. 11.22а).

2) Точка не принадлежит треугольнику но лежит в плоскости этого треугольника. Тогда снова выпуклую оболочку системы получим, соединяя точку с точками треугольника (рис. 11.22 б). В результате получим либо выпуклый четырехугольник

Рис. 11.22

Рис. 11.23

Рис. 11.24

либо треугольник, одной из вершин которого является , а две другие вершины лежат в двух из трех точек (рис. 11.22в).

3) Точка не принадлежит плоскости треугольника (рис. 11.23). Выпуклой оболочкой точек в этом случае является тетраэдр который заполнят отрезки, соединяющую точку с точками треугольника (рис. 11.24).

Проведенные построения подсказывают, как построить выпуклую оболочку F системы S, состоящей из точки надо найти сначала выпуклую оболочку G точек а затем соединить отрезками точку со всеми точками фигуры G (рис. 11.25). Эти отрезки и заполнят выпуклую оболочку F системы

Выделим это утверждение как лемму и докажем ее.

Лемма (о выпуклой оболочке конечного числа точек). Выпуклая оболочка F системы точек является фигурой, заполненной отрезками, которые соединяют точку со всеми точками выпуклой оболочки G системы точек

Рис. 11.25

Рис. 11.26

Обозначим через Н фигуру, заполненную отрезками, которые соединяют точку со всеми точками фигуры G (рис. 11.25). Покажем, что фигура Н — выпукла. Возьмем любые две ее точки X, Y. Они лежат на отрезках идущих из точки в некоторые точки А, В фигуры G. Так как G — выпуклая фигура, то она содержит отрезок АВ (рис. 11.26). Но тогда все отрезки, идущие из в точки отрезка АВ, содержатся в Н, а потому и весь треугольник содержится в Н. Поскольку отрезок XY содержится в треугольнике то XY содержится и в Н. Итак, Н содержит отрезок, соединяющий любые две точки фигуры Н, т.е. Н — выпуклая фигура.

Итак, Н — выпуклая фигура, содержащая точки Поэтому Н содержит выпуклую оболочку точек

С другой стороны, Н состоит из отрезков, каждый из которых, очевидно, содержится в F. Поэтому Н содержится в F. Следовательно, Н и F совпадают.

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

Рис. 11.27

Рис. 11.28

лежат разве лишь в точках (может быть не во всех из них, рис. 11.27).

Действительно, такой многоугольник является объединением конечного числа треугольников, имеющих общую вершину две другие вершины лежат в остальных точках данной системы.

Если же точки не лежат в одной плоскости, то их выпуклой оболочкой является выпуклый многогранник. Он может быть получен объединением тетраэдров, имеющих общую вершину , три другие вершины которых лежат в остальных точках данной системы. Вершины этого многогранника лежат разве лишь в точках данной системы (рис. 11.28).

В завершение этого пункта докажем теорему, обратную, в известном смысле, предложениям, установленным выше.

Теорема (о задании выпуклого многогранника своими вершинами). Выпуклый многогранник (а также и выпуклый многоугольник) есть выпуклая оболочка своих вершин и, следовательно, полностью определяется своими вершинами.

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

Рис. 11.29

Рис. 11.30

Пусть А — какая-либо точка выпуклого многогранника Р. Если она лежит на его ребре, то она, очевидно, принадлежит выпуклой оболочке вершин этого ребра. Если точка А лежит внутри грани Q, то проведем через нее отрезок до пересечения с границей грани Q. Тогда концы этого отрезка лежат на ребрах и, следовательно, принадлежат выпуклой оболочке вершин. Но в таком случае и сам отрезок, а вместе с ним и точка А принадлежат этой выпуклой оболочке.

Наконец, если точка А лежит внутри многогранника Р, то проводим через нее отрезок до пересечения его с границей многогранника. Тогда, по доказанному, концы этого отрезка принадлежат выпуклой оболочке вершин и, значит, сам отрезок, а вместе с ним и точка принадлежат этой выпуклой оболочке.

Замечание. Доказывая эту теорему для многогранника, мы попутно доказали ее утверждение и для многоугольника.