Encerramento com soma de Minkowski.

10

A soma de Minkowski de dois conjuntos de vetores é dada porUMA,B∈Rd

UMA⊕B={uma+b∣uma∈UMA,b∈B}

Acabei de ouvir um problema interessante (atribuído a Dan Halperin): Dada a forma , existe uma forma tal que ?A A ⊕ A = BBUMAUMA⊕UMA=B

Mas essa não é minha pergunta (parece ser um problema em aberto). Observe que no problema acima, se é um conjunto convexo, existe uma solução pois os conjuntos convexos são fechados sob a soma de Minkowski.A = ( 1 / 2 ) BBUMA=(1 1/2)B

Corrija uma classe de formas . Dizemos que está fechado em Minkowski, se houver algum .SSSUMA,B∈S,UMA⊕B∈S

Então, minha pergunta é:

Existe uma boa caracterização de classes de formas que são fechadas sob somas de Minkowski?S

cg.comp-geom Suresh Venkat
fonte
Jukka: Eu atualizei a pergunta.
Suresh Venkat
11
Li a revisão 2. (1) Não vejo como “conjuntos convexos são fechados sob a soma de Minkowski” é a razão para “existe uma solução A = (1/2) B” (embora ambos os fatos sejam claros). (2) Duvido que exista uma caracterização equivalente melhor do que “fechada sob as somas de Minkowski”.
Tsuyoshi Ito 01/03
É verdade que não há uma implicação direta. Mas a prova usa o fato de que a soma de dois conjuntos convexos é convexa. Eu poderia reformular a dizer "note também que .." em vez de "desde que ..."
Suresh Venkat
2
Eu não acho que usamos o fato de que a soma de Minkowski de dois conjuntos convexos é convexa ao provar (B / 2) ⊕ (B / 2) = B para um conjunto convexo B. A contenção (B / 2) ⊕ (B / 2) ⊇B não tem nada a ver com convexidade. A contenção (B / 2) ⊕ (B / 2) followsB decorre do fato de B ser convexo: para qualquer x, y∈B, (x / 2) + (y / 2) becauseB devido à convexidade de B.
Tsuyoshi Ito 01/03
11
@ Yoshio: é possível. Esta questão também pode estar relacionada ao trabalho 'sumset' em grupos gerais.
Suresh Venkat

Respostas:

6

Reticulados e subespaços lineares são fechados na soma de Minkowski. Isso é mais ou menos imediato da definição deles. Reticulados + subespaços lineares são fechados na soma de Minkowski (ou seja, um membro desse conjunto é, por exemplo, um conjunto de linhas paralelas na distância 1 um do outro). Polígonos conectados com furos são fechados na soma de Minkowski. Os anéis [as diferenças definidas de dois discos concêntricos] são fechados sob a soma de Minkowski (um disco é considerado um anel, naturalmente). O conjunto de segmentos de linha paralelos a uma determinada direção é fechado na soma de Minkowski. As batatas amassadas são fechadas sob a soma de Minkowski, mas apenas se estiverem bem cozidas (ou talvez não, seja tarde demais) ...

Além disso, a família de união finita de anéis concêntricos é fechada sob a soma de Minkowski.

Sariel Har-Peled
fonte