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

Определения и обозначения

Выпуклое множество — множество, в котором для любых двух точек весь соединяющий их отрезок тоже принадлежит множеству. На плоскости это, например, круг или треугольник вместе с внутренними точками; в пространстве — шар или куб. У кольца и полумесяца это свойство нарушается: найдутся две точки, отрезок между которыми проходит снаружи.

Выпуклая оболочка набора точек — наименьшее выпуклое множество, содержащее их. «Наименьшее» означает, что оболочка включает только то, что необходимо, чтобы множество исходных точек стало выпуклым: например, для трёх не лежащих на одной прямой точек она заполняет треугольник, а не только его стороны.

Выпуклая комбинация точек — сумма этих точек с неотрицательными коэффициентами, сумма которых равна единице. Коэффициенты задают доли, в которых точки участвуют: две точки дают точку отрезка, три — точку треугольника. Благодаря условиям на коэффициенты результат не «уходит» за пределы выпуклой оболочки.

Выпуклый многогранник — ограниченное выпуклое тело, граница которого состоит из многоугольных граней. Выпуклость здесь означает, что отрезок между любыми двумя точками тела остаётся внутри него. Например, куб — выпуклый многогранник, а тело с выемкой не проходит отрезочную проверку.

Как это устроено

Отрезочный признак переводит общее свойство выпуклости в проверку любых двух точек. Если хотя бы для одной пары часть отрезка выходит из тела, оно невыпуклое; если для каждой пары отрезок остаётся внутри, выполнено определение выпуклого множества. Поэтому не достаточно проверить только вершины или несколько отдельных отрезков: проверка относится ко всем точкам тела.

Выпуклые комбинации наглядно объясняют, откуда берутся точки оболочки. Для A и B выражение (1 − t)A + tB при 0 ≤ t ≤ 1 задаёт точку отрезка AB; для трёх точек коэффициенты образуют доли, сумма которых равна единице, и задают точку треугольника. Для многогранника таким же способом комбинируют его вершины. Отрицательный коэффициент может вынести точку за пределы фигуры, а сумма, отличная от единицы, перестаёт задавать нужное усреднение.

Чтобы построить оболочку конечного набора, берут все выпуклые комбинации этих точек. Получившееся множество содержит исходные точки: для каждой из них можно поставить коэффициент 1, а остальным — 0. Оно выпукло, поскольку отрезок между двумя такими комбинациями снова является комбинацией исходных точек. Любое выпуклое множество, содержащее исходные точки, обязано содержать и все эти комбинации, поэтому оболочка действительно наименьшая.

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

Грани, рёбра и вершины — элементы границы многогранника, но его выпуклость накладывает на них общее условие. Плоскость каждой грани является опорной: весь многогранник лежит в одном из двух полупространств, ограниченных этой плоскостью. Если точки многогранника оказались по разные стороны, такая плоскость не может задавать его грань. Это даёт способ проверять предполагаемые грани по координатам.

Выпуклость, выпуклая оболочка и выпуклый многогранник

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

Разбор задач

1. Треугольная пирамида

Условие. Определить, выпукла ли треугольная пирамида, и обосновать ответ через отрезки между её точками. Рассматриваем пирамиду вместе с внутренними точками, а не только её поверхность. Нужно проверить признак выпуклости для любых двух точек тела.

1. Обозначим вершины пирамиды A, B, C, D. Внутренность пирамиды — выпуклая оболочка этих четырёх вершин.
2. Любые две точки пирамиды можно представить выпуклыми комбинациями A, B, C, D. Точки на отрезке между ними также являются выпуклыми комбинациями тех же вершин.
3. Значит, весь соединяющий точки отрезок остаётся в пирамиде. Это верно для любой пары, поэтому выполнен отрезочный признак.

Ответ: треугольная пирамида выпукла.

2. Четыре точки в одной плоскости

Условие. Даны A(0; 0), B(4; 0), C(0; 4), D(1; 1). Определить вершины их выпуклой оболочки и проверить, лежит ли одна из точек внутри. Удобно сначала проверить, можно ли выразить D через три остальные точки с допустимыми коэффициентами.

1. Рассмотрим комбинацию ½A + ¼B + ¼C. Её координаты равны (½·0 + ¼·4 + ¼·0; ½·0 + ¼·0 + ¼·4) = (1; 1).
2. Коэффициенты неотрицательны и дают в сумме 1, поэтому D — выпуклая комбинация A, B, C. Значит, D находится внутри треугольника ABC.
3. Точки A, B и C не лежат на одной прямой, а каждая задаёт угол этого треугольника. Поэтому их оболочка — треугольник ABC, и D не добавляет новой вершины.

Ответ: вершины оболочки — A, B, C; D лежит внутри неё.

3. Пять точек в пространстве

Условие. Даны A(0; 0; 0), B(1; 0; 0), C(0; 1; 0), D(0; 0; 1), E(¼; ¼; ¼). Найти вершины и описать грани оболочки. Проверим, выражается ли E как выпуклая комбинация первых четырёх точек.

1. Имеем E = ¼A + ¼B + ¼C + ¼D. Все коэффициенты неотрицательны, их сумма равна 1, поэтому E принадлежит тетраэдру ABCD.
2. Точки A, B, C, D не лежат в одной плоскости и образуют тетраэдр. Точка E лежит внутри него, поэтому не становится вершиной оболочки.
3. Плоскости граней задаются уравнениями z = 0, y = 0, x = 0 и x + y + z = 1. В каждой из этих плоскостей лежат три вершины тетраэдра, а остальные вершины находятся по одну сторону.

Ответ: вершины оболочки — A, B, C, D; грани — ABC, ABD, ACD и BCD; E находится внутри.

Типичные ошибки

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

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

Забывать, что сумма коэффициентов равна единице. Даже при неотрицательных коэффициентах комбинация с другой суммой не обязательно задаёт точку оболочки. Это условие пропускают, сосредоточившись на вычислении координат. Сложите коэффициенты и убедитесь, что результат равен 1.

Считать вершиной каждую точку набора. Точка может быть выпуклой комбинацией других точек и лежать внутри оболочки или на её грани. Ошибка возникает из-за смешения исходного набора с набором вершин. Проверьте, можно ли представить точку комбинацией остальных: если можно, она не является крайней вершиной оболочки.

Связь с другими темами

Для этой темы нужны понятия отрезка, плоскости, многоугольника, многогранника, его вершин, рёбер и граней. Выпуклые комбинации связаны с линейными комбинациями и координатным методом: координаты результата получают теми же действиями с коэффициентами. Эта связь помогает проверять положение точки и строить оболочки по координатам. Далее понятия выпуклости применяются в стереометрии и задачах о многогранниках, а оболочка помогает находить наименьшее выпуклое тело, содержащее заданные точки.

Что запомнить

• Выпуклое множество содержит отрезок между любой парой своих точек.
• Коэффициенты выпуклой комбинации неотрицательны и в сумме равны единице.
• Выпуклая оболочка — наименьшее выпуклое множество, содержащее заданные точки.
• Выпуклая оболочка конечного набора точек состоит из их выпуклых комбинаций.
• Не каждая точка набора обязательно является вершиной его выпуклой оболочки.
• Выпуклый многогранник лежит по одну сторону от плоскости каждой своей грани.