Zamknięcie w ramach sumy Minkowskiego.

Sumę Minkowskiego dwóch zbiorów wektorów podaje $A, B \in R^d$

A \oplus B = {a + b ∣ a \in A, b \in B}

$A \oplus B = \{ a + b \mid a \in A, b \in B \}$

Właśnie usłyszałem interesujący problem (przypisany Danowi Halperinowi): Czy mając kształt , istnieje taki kształt , że ? $B$ $A$ $A \oplus A = B$

Ale to nie moje pytanie (wydaje się, że jest to otwarty problem). Zauważ, że w powyższym problemie, jeśli jest zbiorem wypukłym, istnieje rozwiązanie ponieważ zbiory wypukłe są zamknięte przy uwzględnieniu sum Minkowskiego. $B$ $A = (1/2)B$

Napraw klasę kształtów . Mówimy, że jest zamknięty w ramach sum Minkowskiego, jeśli dla dowolnego . ${\cal S}$ ${\cal S}$ $A, B \in {\cal S}, A \oplus B \in {\cal S}$

Więc moje pytanie brzmi:

Czy istnieje ładna charakterystyka klas kształtów zamkniętych pod sumami Minkowskiego? ${\cal S}$

cg.comp-geom Suresh Venkat
źródło

Jukka: Zaktualizowałem pytanie.

Suresh Venkat

Przeczytałem wersję 2. (1) Nie widzę, jak „zbiory wypukłe są zamykane przy obliczaniu sum Minkowskiego” jest przyczyną „istnieje rozwiązanie A = (1/2) B” (chociaż oba fakty są jasne). (2) Wątpię, czy istnieje jakakolwiek równoważniejsza charakterystyka ładniejsza niż „zamknięta pod sumami Minkowskiego”.

Tsuyoshi Ito

To prawda, że nie ma to bezpośredniego wpływu. Ale dowód wykorzystuje fakt, że suma dwóch zbiorów wypukłych jest wypukła. Mógłbym przeformułować, aby powiedzieć „też zwróć uwagę…” zamiast „od ...”

Suresh Venkat

Nie sądzę, abyśmy korzystali z faktu, że suma Minkowskiego dwóch zbiorów wypukłych jest wypukła, gdy dowodzi się (B / 2) ⊕ (B / 2) = B dla zbioru wypukłego B. Ograniczenie (B / 2) ⊕ (B / 2) ⊇B nie ma nic wspólnego z wypukłością. Ograniczenie (B / 2) ⊕ (B / 2) ⊆B wynika z faktu, że B jest wypukły: dla dowolnego x, y∈B, (x / 2) + (y / 2) becauseB z powodu wypukłości B.

Tsuyoshi Ito

@Yoshio: jest to możliwe. Pytanie to można również powiązać z pracą „sumset” również w grupach ogólnych.

Suresh Venkat

Kraty i podprzestrzenie liniowe są zamknięte pod sumą Minkowskiego. To mniej więcej bezpośrednio od ich definicji. Kraty + podprzestrzenie liniowe są zamknięte pod sumą Minkowskiego (tj. Członkiem tego zbioru jest na przykład zbiór równoległych linii w odległości 1 od siebie). Połączone wielokąty z otworami są zamknięte pod sumą Minkowskiego. Pierścienie [ustawione różnice dwóch koncentrycznych dysków] są zamknięte pod sumą Minkowskiego (dysk jest oczywiście uważany za pierścień). Zbiór odcinków linii równoległych do określonego kierunku jest zamknięty pod sumą Minkowskiego. Mushed ziemniaki są zamknięte pod sumą Minkowskiego, ale tylko wtedy, gdy są dobrze ugotowane (a może nie, jest za późno) ...

Również rodzina skończonego związku koncentrycznych pierścieni jest zamknięta pod sumą Minkowskiego.

Sariel Har-Peled
źródło

Zamknięcie w ramach sumy Minkowskiego.

Odpowiedzi: