Schließung unter Minkowski-Summe.

10

Die Minkowski-Summe zweier Sätze von Vektoren ist gegeben durchA,B∈Rd

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

Ich habe gerade ein interessantes Problem gehört (Dan Halperin zugeschrieben): Gibt es bei einer Form eine Form so dass ?BAA⊕A=B

Aber das ist nicht meine Frage (es scheint ein offenes Problem zu sein). Beachten Sie, dass in dem obigen Problem, wenn eine konvexe Menge ist, eine Lösung da konvexe Mengen unter der Aufnahme von Minkowski-Summen geschlossen werden.BA=(1/2)B

Korrigieren Sie eine Klasse von Formen . Wir sagen, dass unter Minkowski-Summen geschlossen ist, wenn für .SSA,B∈S,A⊕B∈S

Meine Frage lautet also:

Gibt es eine schöne Charakterisierung von Klassen von Formen , die unter Minkowski-Summen geschlossen sind?S

cg.comp-geom Suresh Venkat
quelle
Jukka: Ich habe die Frage aktualisiert.
Suresh Venkat
1
Ich habe die Revision 2 gelesen. (1) Ich sehe nicht, wie „konvexe Mengen unter Minkowski-Summen geschlossen werden“ der Grund für „es gibt eine Lösung A = (1/2) B“ ist (obwohl beide Fakten klar sind). (2) Ich bezweifle, dass es eine äquivalente Charakterisierung gibt, die besser ist als "unter Minkowski-Summen geschlossen".
Tsuyoshi Ito
Es ist wahr, dass es keine direkte Implikation gibt. Der Beweis nutzt jedoch die Tatsache, dass die Summe zweier konvexer Mengen konvex ist. Ich könnte umformulieren, um zu sagen "auch beachten, dass .." anstelle von "seit ..."
Suresh Venkat
2
Ich denke nicht, dass wir die Tatsache verwenden, dass die Minkowski-Summe zweier konvexer Mengen konvex ist, wenn wir (B / 2) ⊕ (B / 2) = B für eine konvexe Menge B beweisen. Das Containment (B / 2) ⊕ (B. / 2) ⊇B hat nichts mit Konvexität zu tun. Das Containment (B / 2) ⊕ (B / 2) ⊆B folgt aus der Tatsache, dass B konvex ist: für jedes x gilt y∈B, (x / 2) + (y / 2) ∈B aufgrund der Konvexität von B.
Tsuyoshi Ito
1
@ Yoshio: Es ist möglich. Diese Frage könnte auch mit der Arbeit in allgemeinen Gruppen zusammenhängen.
Suresh Venkat

Antworten:

6

Gitter und lineare Teilräume werden unter der Minkowski-Summe geschlossen. Das ist mehr oder weniger unmittelbar von ihrer Definition. Gitter + lineare Teilräume werden unter der Minkowski-Summe geschlossen (dh ein Mitglied dieser Menge ist beispielsweise eine Menge paralleler Linien im Abstand 1 voneinander). Verbundene Polygone mit Löchern werden unter der Minkowski-Summe geschlossen. Ringe [die eingestellten Unterschiede zweier konzentrischer Scheiben] werden unter der Minkowski-Summe geschlossen (eine Scheibe wird natürlich als Ring betrachtet). Der Satz von Liniensegmenten parallel zu einer bestimmten Richtung wird unter der Minkowski-Summe geschlossen. Kartoffelbrei sind unter Minkowski-Summe geschlossen, aber nur, wenn sie gut gekocht sind (oder vielleicht auch nicht, es ist zu spät) ...

Auch die Familie der endlichen Vereinigung konzentrischer Ringe ist unter der Minkowski-Summe geschlossen.

Sariel Har-Peled
quelle