Cierre bajo la suma de Minkowski.

10

La suma de Minkowski de dos conjuntos de vectores viene dada porA,B∈Rd

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

Acabo de escuchar un problema interesante (atribuido a Dan Halperin): Dada una forma , ¿existe una forma A tal que A ⊕ A = B ?BAA⊕A=B

Pero esa no es mi pregunta (parece ser un problema abierto). Observe que en el problema anterior, si es un conjunto convexo, entonces existe una solución A = ( 1 / 2 ) B desde conjuntos convexos son cerrados bajo la toma de sumas Minkowski.BA=(1/2)B

Fijar una clase de formas . Se dice que S es cerrado bajo sumas Minkowski si por alguna A , B ∈ S , A ⊕ B ∈ S .SSA,B∈S,A⊕B∈S

Entonces mi pregunta es:

¿Existe una buena caracterización de las clases de formas que están cerradas bajo las sumas de Minkowski?S

cg.comp-geom Suresh Venkat
fuente
Jukka: Actualicé la pregunta.
Suresh Venkat
1
Leí la revisión 2. (1) No veo cómo "los conjuntos convexos se cierran al tomar sumas de Minkowski" es la razón de que "existe una solución A = (1/2) B" (aunque ambos hechos son claros). (2) Dudo que haya una caracterización equivalente mejor que "cerrada bajo las sumas de Minkowski".
Tsuyoshi Ito
Es cierto que no hay una implicación directa. Pero la prueba utiliza el hecho de que la suma de dos conjuntos convexos es convexa. Podría reformular para decir "también tenga en cuenta que ..." en lugar de "desde ..."
Suresh Venkat
2
No creo que usemos el hecho de que la suma de Minkowski de dos conjuntos convexos es convexa cuando se prueba (B / 2) ⊕ (B / 2) = B para un conjunto convexo B. La contención (B / 2) ⊕ (B / 2) ⊇B no tiene nada que ver con la convexidad. La contención (B / 2) ⊕ (B / 2) ⊆B se deduce del hecho de que B es convexo: para cualquier x, y∈B, (x / 2) + (y / 2) ∈B debido a la convexidad de B.
Tsuyoshi Ito
1
@Yoshio: es posible. Esta pregunta también podría estar relacionada con el trabajo 'sumset' en grupos generales también.
Suresh Venkat

Respuestas:

6

Los enrejados y subespacios lineales están cerrados bajo la suma de Minkowski. Eso es más o menos inmediato de su definición. Los enrejados + subespacios lineales están cerrados bajo la suma de Minkowski (es decir, un miembro de este conjunto es, por ejemplo, un conjunto de líneas paralelas en la distancia 1 entre sí). Los polígonos conectados con agujeros están cerrados bajo la suma de Minkowski. Los anillos [las diferencias establecidas de dos discos concéntricos] se cierran bajo la suma de Minkowski (un disco se considera un anillo, naturalmente). El conjunto de segmentos de línea paralelos a una determinada dirección se cierra bajo la suma de Minkowski. Las papas picadas se cierran bajo la suma de Minkowski, pero solo si están bien cocidas (o tal vez no, es demasiado tarde) ...

Además, la familia de la unión finita de anillos concéntricos está cerrada bajo la suma de Minkowski.

Sariel Har-Peled
fuente