Геометрия · объяснение и практика

Когда пересечение каждых трёх выпуклых областей гарантирует общее пересечение

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

Синий треугольник обозначает свой прямой угол оранжевым квадратом.

В теме Выпуклость и геометрические оценки · Учебная карта

В маршруте Выпуклость и геометрия решётки · 10 тем

Главная мысль

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

Общая точка тройки сильнее трёх пар

Представим несколько допустимых областей для расположения одного объекта. Требуется одна точка, принадлежащая всем одновременно. Теорема Хелли утверждает, что для конечного семейства выпуклых множеств на плоскости достаточно проверить каждую тройку. У разных троек свидетелями могут быть разные точки: условие не требует заранее найти одну общую для всех.

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

Три диска показывают недостаточность пар

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

Действительно, для центра тяжести G и любой P сумма квадратов расстояний до трёх вершин равна 3|PG|²+4 и не меньше четырёх. При принадлежности всем дискам она была бы не больше 3·1,1²=3,63. Противоречие доказывает отсутствие общего пересечения независимо от неточности нарисованных кругов.

Пример

Чем этот пример отличается от нарушения теоремы Хелли?

Единственная тройка дисков не имеет общей точки, поэтому нужное условие теоремы просто не выполнено. Выполнены лишь более слабые попарные проверки.

Конечность и размерность не являются украшениями

Для бесконечного семейства без дополнительных условий вывод неверен. Например, полуплоскости x≥n при всех положительных целых n выпуклы, и любая конечная подсемья имеет общие точки, но общего конечного x для всех не существует. Поэтому конечный список ограничений и бесконечная система требуют разных оговорок.

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

От чтения к действию

А теперь — вы

Даны семь выпуклых областей на плоскости. У каждой тройки есть общая точка. Что гарантирует теорема Хелли?

Частые вопросы

Должна ли одна и та же точка подходить всем проверенным тройкам?

Нет. Каждая тройка может иметь своего свидетеля; теорема гарантирует существование общей точки всего конечного семейства.

Почему нельзя ограничиться парами?

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

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться