Закрытие по сумме Минковского.

10

Сумма Минковского двух множеств векторов имеет видA,B∈Rd

A⊕B={a+b∣a∈A,b∈B}

Я только что услышал интересную проблему (приписываемое Dan Гальперина): Учитывая форма , существует ли форма А такое , что A ⊕ A = B ?BAA⊕A=B

Но это не мой вопрос (кажется, это открытая проблема). Заметим , что в указанной выше проблемы, если есть множество выпукло, то существует решение А = ( 1 / 2 ) B , поскольку выпуклые множества замкнуты относительно взятия сумм Минковского.BA=(1/2)B

Фиксируем класс формы . Мы говорим , что S будет закрыто под суммами Минковского , если для любого A , B ∈ S , ⊕ B ∈ S .SSA,B∈S,A⊕B∈S

Итак, мой вопрос:

Есть ли хорошая характеристика классов форм , замкнутых по суммам Минковского?S

cg.comp-geom Суреш Венкат
источник
Юкка: я обновил вопрос.
Суреш Венкат
1
Я читаю редакцию 2. (1) Я не вижу, как «выпуклые множества замкнуты при взятии сумм Минковского», является причиной «существует решение A = (1/2) B» (хотя оба факта очевидны). (2) Я сомневаюсь, что есть эквивалентная характеристика, более приятная, чем «замкнутая по суммам Минковского».
Tsuyoshi Ito
Это правда, что нет прямого следствия. Но доказательство использует тот факт, что сумма двух выпуклых множеств является выпуклой. Я мог бы перефразировать слова «также обратите внимание, что…» вместо «с тех пор, как…»
Суреш Венкат
2
Я не думаю, что мы используем тот факт, что сумма Минковского двух выпуклых множеств является выпуклой при доказательстве (B / 2) ⊕ (B / 2) = B для выпуклого множества B. Содержимое (B / 2) ⊕ (B / 2) ⊇B не имеет ничего общего с выпуклостью. Содержимое (B / 2) ⊕ (B / 2) ⊆B следует из того факта, что B выпуклый: для любого x, y∈B, (x / 2) + (y / 2) ∈B из-за выпуклости B.
Tsuyoshi Ito
1
@Yoshio: это возможно. Этот вопрос также может быть связан с работой "sumset" в общих группах.
Суреш Венкат

Ответы:

6

Решетки и линейные подпространства замкнуты по сумме Минковского. Это более или менее непосредственно из их определения. Решетки + линейные подпространства замкнуты по сумме Минковского (т. Е. Членом этого набора является, например, набор параллельных линий на расстоянии 1 друг от друга). Связные многоугольники с дырками замкнуты по сумме Минковского. Кольца [разности множеств двух концентрических дисков] замкнуты по сумме Минковского (естественно, диск считается кольцом). Множество отрезков, параллельных определенному направлению, замыкаются суммой Минковского. Картофельное пюре закрывают по сумме Минковского, но только если они хорошо приготовлены (а может и нет, уже слишком поздно) ...

Также семейство конечных объединений концентрических колец замкнуто относительно суммы Минковского.

Сариэль Хар-Пелед
источник