Геометрия · объяснение и практика
Почему точке выпуклой оболочки на плоскости достаточно трёх опорных точек
Почему любую точку плоской выпуклой оболочки можно представить через не более трёх исходных точек и как убрать лишние веса, не выбрав произвольную неподходящую тройку.

В теме Выпуклость и геометрические оценки · Учебная карта
В маршруте Выпуклость и геометрия решётки · 10 тем
Главная мысль
На плоскости каждая точка выпуклой оболочки множества является выпуклой комбинацией не более трёх его точек. Теорема гарантирует существование подходящей тройки, а не пригодность любой выбранной.
Выпуклая комбинация накладывает два условия
Точка P является выпуклой комбинацией X₁,…,Xₘ, если P=ΣλᵢXᵢ при λᵢ≥0 и Σλᵢ=1. Первое условие не позволяет уйти за выбранные точки отрицательным весом, второе нормирует среднее. Выпуклая оболочка множества состоит из всех таких конечных комбинаций его точек.
Теорема Каратеодори утверждает, что в двумерном пространстве для любой P достаточно трёх или меньшего числа исходных точек. Если P лежит на подходящем отрезке, хватает двух, а если совпадает с одной из исходных — одной. Три здесь верхняя граница необходимого количества, а не обязательное число положительных весов.
Лишние веса можно исключить без изменения точки
Если в плоской комбинации больше трёх положительных весов, соответствующие расширенные векторы (xᵢ,yᵢ,1) линейно зависимы в трёхмерном пространстве. Значит, существует ненулевая поправка весов с нулевой суммой и нулевым изменением обеих координат. Двигаясь по ней до первого нулевого веса, можно уменьшить число участвующих точек.
Все остальные веса при подходящем выборе величины шага остаются неотрицательными. Процесс повторяют, пока не останется не более трёх. Это объясняет, почему результат зависит от размерности. Простое удаление любого маленького веса без компенсации не подходит: сумма весов и положение P тогда изменятся.
Пример
В квадрате A=(0,0),B=(4,0),C=(4,4),D=(0,4) точка P=(2,1) записана весами 3/8,3/8,1/8,1/8. Найдите запись через три вершины.
Подходит P=(1/2)A+(1/4)B+(1/4)C. Веса неотрицательны, суммируются в единицу и дают координаты (2,1), поэтому D можно исключить с перераспределением.
Подходящая тройка не обязана быть заранее удобной
В том же квадрате точка возле C может не лежать в треугольнике ABD. Поэтому нельзя произвольно выбрать три вершины и сослаться на теорему. Нужно проверить включение P в их треугольник либо получить комбинацию последовательным исключением. Существование малого представления не сообщает, какие именно точки его образуют.
Коллинеарная тройка не создаёт двумерного треугольника, но может корректно представить точку на отрезке. Кроме того, теорема не утверждает единственности комбинации: в квадрате центральная точка имеет несколько разных представлений. Прикладной смысл результата — возможность сократить сертификат включения в оболочку, сохранив явные неотрицательные веса и исходные точки.
От чтения к действию
А теперь — вы
Частые вопросы
Должны ли все три веса быть положительными?
Нет. Можно использовать меньше трёх точек; нулевые веса просто исключают ненужные элементы.
Гарантирует ли теорема единственное представление?
Нет. Разные тройки и даже разные пары могут представлять одну точку, если геометрия исходного множества это допускает.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как площади задают барицентрические координаты точки
Как три веса при вершинах задают точку треугольника, связать их с противоположными площадями и не перепутать однородную тройку с обычными декартовыми координатами.
Открыть темуКогда пересечение каждых трёх выпуклых областей гарантирует общее пересечение
Когда можно заменить проверку общего пересечения конечного семейства выпуклых областей проверкой троек и почему попарного пересечения на плоскости недостаточно.
Открыть тему