Fermeture sous la somme de Minkowski.

10

La somme de Minkowski de deux ensembles de vecteurs est donnée parA,B∈Rd

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

Je viens d'entendre un problème intéressant (attribué à Dan Halperin): étant donné une forme , existe-t-il une forme telle que ?A A ⊕ A = BBAA⊕A=B

Mais ce n'est pas ma question (cela semble être un problème ouvert). Remarquez que dans le problème ci-dessus, si est un ensemble convexe, alors il existe une solution puisque les ensembles convexes sont fermés sous la prise de sommes de Minkowski.A = ( une / 2 ) BBA=(1/2)B

Corrige une classe de formes . Nous disons que est fermé sous les sommes de Minkowski si pour tout .S A , B ∈ S , A ⊕ B ∈ SSSA,B∈S,A⊕B∈S

Ma question est donc:

Y a-t-il une bonne caractérisation des classes de formes qui sont fermées sous les sommes de Minkowski?S

cg.comp-geom Suresh Venkat
la source
Jukka: J'ai mis à jour la question.
Suresh Venkat
1
J'ai lu la révision 2. (1) Je ne vois pas comment «les ensembles convexes sont fermés en prenant des sommes de Minkowski» est la raison pour laquelle «il existe une solution A = (1/2) B» (bien que les deux faits soient clairs). (2) Je doute qu'il existe une caractérisation équivalente plus agréable que «fermé sous les sommes de Minkowski».
Tsuyoshi Ito
C'est vrai qu'il n'y a pas d'implication directe. Mais la preuve utilise le fait que la somme de deux ensembles convexes est convexe. Je pourrais reformuler pour dire "notez aussi que .." au lieu de "depuis ..."
Suresh Venkat
2
Je ne pense pas que nous utilisons le fait que la somme de Minkowski de deux ensembles convexes est convexe lors de la démonstration (B / 2) ⊕ (B / 2) = B pour un ensemble convexe B. Le confinement (B / 2) ⊕ (B / 2) ⊇B n'a rien à voir avec la convexité. Le confinement (B / 2) ⊕ (B / 2) ⊆B résulte du fait que B est convexe: pour tout x, y∈B, (x / 2) + (y / 2) ∈B en raison de la convexité de B.
Tsuyoshi Ito
1
@Yoshio: c'est possible. Cette question pourrait également être liée au travail «sommaire» dans des groupes généraux.
Suresh Venkat

Réponses:

6

Les réseaux et les sous-espaces linéaires sont fermés sous la somme de Minkowski. C'est plus ou moins immédiat de leur définition. Les réseaux + sous-espaces linéaires sont fermés sous la somme de Minkowski (c'est-à-dire qu'un membre de cet ensemble est par exemple un ensemble de lignes parallèles distantes de 1). Les polygones connectés avec des trous sont fermés sous la somme de Minkowski. Les anneaux [les différences définies de deux disques concentriques] sont fermés sous la somme de Minkowski (un disque est considéré comme un anneau, naturellement). L'ensemble des segments de ligne parallèles à une certaine direction est fermé sous la somme de Minkowski. Les pommes de terre musclées sont fermées sous la somme de Minkowski, mais seulement si elles sont bien cuites (ou peut-être pas, il est trop tard) ...

De plus, la famille d'union finie d'anneaux concentriques est fermée sous la somme de Minkowski.

Sariel Har-Peled
la source