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

Как сумма множеств складывает положения, а не площади

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

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

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

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

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

Сумма Минковского A+B состоит из всех a+b при a∈A,b∈B. Это операция над положениями точек; её площадь обычно не равна сумме площадей исходных фигур.

Складываем каждую возможную пару точек

Пусть A — горизонтальный отрезок от (0,0) до (3,0), а B — вертикальный отрезок от (0,0) до (0,2). Любая сумма имеет вид (x,y), где 0≤x≤3 и 0≤y≤2. Поэтому результатом служит весь прямоугольник 3 на 2, а не только две исходные линии.

У обоих отрезков плоская площадь нулевая, но площадь суммы равна шести. Уже этот пример показывает, почему площадь суммы Минковского не вычисляют простым сложением площадей. Объединение A∪B тоже отличается: оно оставляет лишь точки хотя бы одного отрезка, не создавая новых парных координат.

Сложение с одной точкой является переносом

Если B состоит только из одного вектора t, множество A+B равно переносу A на t. Если вместо одной точки B содержит целую область, получается объединение всех таких переносов A. Для двух дисков радиусов r₁,r₂ сумма является диском радиуса r₁+r₂ с центром в сумме их центров.

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

Пример

Сложите диск радиуса 2 с центром (1,0) и диск радиуса 3 с центром (0,4).

Получится диск радиуса пять с центром (1,4). Координаты центров складываются как векторы, а положительные радиусы — как границы возможных радиальных смещений.

Геометрический запас зависит от модели второй фигуры

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

Сумма коммутативна, потому что a+b=b+a. Но множество нельзя просто заменить своей границей без проверки: заполнение существенно для результата. Если складываются два выпуклых множества, сумма тоже выпукла, поскольку выпуклая комбинация двух сумм раскладывается в сумму двух допустимых выпуклых комбинаций. Для невыпуклых исходных множеств такого общего обещания уже нет.

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

А теперь — вы

К диску радиуса 4 прибавляют в смысле Минковского диск радиуса 1 с центром в начале. Как изменится радиус результата?

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

Почему результат может иметь площадь, когда исходные множества её не имеют?

Разные независимые направления двух отрезков создают все точки двумерного прямоугольника; операция объединения так не работает.

Что даёт сложение с одной точкой?

Обычный перенос исходного множества на вектор этой точки, без изменения его размеров и формы.

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

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

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