Alicatar un polígono ortogonal con cuadrados

12

Dado un polígono ortogonal (un polígono cuyos lados son paralelos a los ejes), quiero encontrar el conjunto más pequeño de cuadrados disjuntos interiores, cuya unión es igual al polígono.

Encontré varias referencias a problemas ligeramente diferentes, como:

Estoy buscando un algoritmo para un mosaico mínimo con cuadrados .

Erel Segal-Halevi
fuente
mmm Me imagino que esto es NP-hard. Trataré de formular algo.
Realz Slaw
1
La versión de minimización con agujeros permitidos es NP-Hard, pero para los polígonos ortogonales simplemente conectados (es decir, sin agujeros) tiene un algoritmo polinomial. Sin embargo, si en su problema los tamaños son enteros y realmente quiere decir una cobertura mínima y no una cobertura mínima, entonces en este caso es posible un algoritmo polinomial.
Parham el
Mmm, necesito una prueba de que los cuadrados mínimos estarán posicionados racionalmente y tendrán tamaños racionales; o incluso más, que si la entrada es de tamaño entero y está posicionada entera, entonces los cuadrados mínimos también lo serán (para reducirlo a SAT). Intuitivamente, supongo que esto es cierto, ¿tienes alguna idea para demostrarlo?
Realz Slaw el
@MahmoudAlimohamadi: ¿puede proporcionar los títulos / autores de los trabajos en los que se estudia (y resuelve) el problema de enlosar polígonos rectilíneos (con o sin agujeros) con cuadrados?
Vor
2
por cierto, asumí que quería decir minim um lugar de minim otros .
Realz Slaw

Respuestas:

15

Intentaré mostrar que este problema es NP-hard, mediante la reducción de .Planar-3-SAT


Reducción dePlanar-3-SAT

Algunos gadgets básicos

Los gadgets son configuraciones internas de geometría que nos permitirán construir puertas para usar en un circuito, a lo que reduciremos .Planar-3-SAT

Gadget 4X3

Este gadget tiene dos estados válidos de partición cuadrada mínima :

ingrese la descripción de la imagen aquí         ingrese la descripción de la imagen aquí         ingrese la descripción de la imagen aquí

Izquierda Un gadget 4X3 . Medio y derecho: dos posibles estados mínimos de partición cuadrada .

Gadget 5X4

Este dispositivo es exactamente como un dispositivo 4X3 , solo que con dimensiones más grandes.

ingrese la descripción de la imagen aquí         ingrese la descripción de la imagen aquí         ingrese la descripción de la imagen aquí

Izquierda A 5X4-gadget . Medio y derecho: dos posibles estados mínimos de partición cuadrada .

gadget de punto final

Un dispositivo de punto final es un dispositivo 5X4 . Se usa con frecuencia como punto final / pin de una puerta . Uno de los dos estados de un punto final se puede valorar como verdadero y el otro falso. Marcas de un punto final los dos extremos, uno como y el otro como . El final que está cubierto por el cuadrado grande es el valor del punto final.FTF

ingrese la descripción de la imagen aquí

Izquierda: Estructura metálica del dispositivo de punto final . Centro: punto final de verdadero valor. Derecha: punto final de valor falso.

gadget i-wire

Un dispositivo i-wire es la abreviatura de cable de implicación .

Reglas:

  • 22 .
  • 3

Ejemplo:

ingrese la descripción de la imagen aquí

72

Así es como se usa:

ingrese la descripción de la imagen aquí         ingrese la descripción de la imagen aquí

Figura 8,9 , izquierda: wireframe i-wire a través de dos puntos finales . Derecha: Unión.

Ahora, si un punto final está en el estado correcto, fuerza al otro punto final a una posición de empuje. Ejemplo:

ingrese la descripción de la imagen aquí         ingrese la descripción de la imagen aquí

Izquierda: diagrama de partición cuadrada; el interruptor izquierdo está abajo, "empuja" todos los cuadrados hacia abajo por el i-wire y finalmente, empuja el otro interruptor ( punto final ). Derecha: diagrama de partición cuadrada; el punto final izquierdo está lleno, "empuja" todos los cuadrados hacia abajo por el i-wire y obliga al punto final de la izquierda a estar "arriba".

A¬BAB simplemente volteando el punto final a la derecha.

Sin embargo, esto deja el caso sin restricciones:

ingrese la descripción de la imagen aquí

Si combinamos dos cables i , podemos obtener una implicación bidireccional, esencialmente una igualdad booleana (in):

ingrese la descripción de la imagen aquí         ingrese la descripción de la imagen aquí

Por lo tanto, dos cables i pueden llevar una relación de igualdad total, como un circuito; de hecho, es un circuito. Usaremos estos pares para construir un cable utilizable .

l12+2

Los cables i se pueden orientar según sea necesario.

cable

Un cable consiste en un par de cables i que están conectados a las mismas puertas en cada punto final.

  • Los cables i son de color rojo y verde.
  • 3 espacios (convención).
  • Cada pin de la puerta tendrá un contacto verde y rojo; un cable debe conectarse correctamente.
  • Regla invariable: un i-wire se empuja en la dirección opuesta del otro i-wire , cada puerta asume esto y se asegura de esto (a menos que se indique lo contrario).
  • Como cada cable contiene una implicación bidireccional, transporta los valores de puerta a puerta como un cable en un circuito.
  • Cada cable debe estar conectado a una puerta en ambos extremos. . De lo contrario, puede arruinar los supuestos de algunas puertas que describo, y la regla invariante anterior; sin embargo, las puertas que tienen puntos finales a través de los cables son seguras: puede conectar cables perdidos a estos puntos finales sin preocuparse de que arruine la puerta.
  • los cables deben tener una longitud impar, incluidos los cables a cualquier circuito al que se conecte; sin embargo, describiré una puerta de salto impar a continuación que permite que un cable de longitud uniforme se vuelva de longitud impar.

Fotos :

ingrese la descripción de la imagen aquí

Arriba: un cable .

ingrese la descripción de la imagen aquí        ingrese la descripción de la imagen aquí

Izquierda y derecha: dos posibles estados mínimos de partición cuadrada de un cable . Tenga en cuenta que si el cable tiene solo esta longitud, no podrá desplazarse hacia la derecha o hacia la izquierda, y tendrá que romper un cuadrado en pedazos más pequeños.

los cables se pueden orientar según sea necesario.

puerta curva : doblar un alambre

ingrese la descripción de la imagen aquí       ingrese la descripción de la imagen aquí

Izquierda: vista de marco de alambre. Derecha: vista de la Unión.

Tenga en cuenta el uso del dispositivo 4X3 . Se utiliza para fijar el cable rojo a una longitud impar.

Los siguientes son los dos posibles estados mínimos de partición cuadrada de la curva:

ingrese la descripción de la imagen aquí         ingrese la descripción de la imagen aquí

Izquierda y derecha: dos posibles estados mínimos de partición de cuadrados cuadrados de un cable de flexión.

La puerta se puede orientar según sea necesario. Obviamente, esta puerta se puede reflejar para trabajar en la otra dirección.

Torciendo un alambre

Es fácil cambiar un cable. Ilustración de estructura metálica:

ingrese la descripción de la imagen aquí

puerta-valor-nombrado

Una puerta de valor con nombre es esencialmente un punto final como una puerta con un contacto de cable:

ingrese la descripción de la imagen aquí

Odd -skip-gate : Odd omitiendo un cable

A veces es inconveniente tener solo cables de longitud impar. Por ejemplo:

ingrese la descripción de la imagen aquí

Como puede ver, esa pequeña extensión es un poco molesta. Aquí hay una solución correspondiente, usando la puerta 4X3 :

ingrese la descripción de la imagen aquí

Entonces, convirtiendo esto en una puerta, obtenemos la puerta de salto impar (en estructura metálica):

ingrese la descripción de la imagen aquí

La puerta se puede orientar según sea necesario.

puerta giratoria: torcer un cable

Algunas veces obtienes los cables i rojos y negros en los lados equivocados para usar con una puerta . En este caso, se proporciona una puerta giratoria para retorcer los cables i rojos y negros a los lados opuestos.

Ilustración de estructura metálica:

ingrese la descripción de la imagen aquí

Convéncete a ti mismo de que funciona:

ingrese la descripción de la imagen aquí         ingrese la descripción de la imagen aquí

A

La puerta se puede orientar según sea necesario.

puerta dividida : dividir un cable

División de un cable, estructura metálica:

ingrese la descripción de la imagen aquí

Convénzase de que funciona:

ingrese la descripción de la imagen aquí

A

ingrese la descripción de la imagen aquí

A

Nota: Cada cable que entra y sale del divisor debe conectarse a un punto final en algún lugar, para mantener el invariante. Alternativamente, puede agregar puntos finales a cada uno de los pares de derivaciones del divisor.

La puerta se puede orientar según sea necesario.

sin puerta

La puerta no toma un cable y emite un cable que tiene las implicaciones inversas. Básicamente es una puerta giratoria, excepto que vuelve a etiquetar los colores de los cables. La no puerta se ve así:

ingrese la descripción de la imagen aquí

Y una vista de los dos estados posibles:

ingrese la descripción de la imagen aquí         ingrese la descripción de la imagen aquí

La puerta se puede orientar según sea necesario.

cláusula-puerta

Para la cláusula-puerta , primero presentamos la cláusula-gadget :

ingrese la descripción de la imagen aquí

3

Así es como se ve la puerta:

3

Explicación:

  1. Comience en la cláusula-gadget y siga las flechas.
  2. Las líneas sin flechas significan que es parte de un circuito, pero la puerta no lo obliga a entrar en un estado.
  3. El estado de la cláusula-gadget obliga a uno de los puntos finales a valorarse como verdadero .

3-CNF

La puerta se puede orientar según sea necesario.

Reducción

Φ(x)Planar-3-SAT

Φ(x)=inCi,C={(xjxkxl)}

Una ayuda visual (fuente original: Terrain Guarding es NP-Hard (PDF) , reproducido en tikz):

ingrese la descripción de la imagen aquí

Luego:

  1. xixxi¬xi
  2. Conecte las puertas entre sí con una no puerta , para que nieguen lógicamente los valores de cada uno.
  3. Coloque los polígonos 'puertas' de las variables en sus ubicaciones en la incrustación plana.
  4. Para cada cláusula, coloque una puerta de cláusula en la ubicación de la cláusula en la incrustación plana.
  5. Usando las puertas descritas anteriormente, conecte todas las variables a sus cláusulas.
  6. Ejecute un algoritmo de parición de mínimos cuadrados en la unión resultante de todos los polígonos de la puerta (todo el circuito).
  7. Si el algoritmo devuelve la suma de todos los tamaños de estado de partición cuadrada mínima de la puerta (restando las esquinas compartidas), entonces es satisfactoria. Si no es satisfactoria, forzará a un dispositivo restringido a dividirse en cuadrados más pequeños, aumentando así el número de cuadrados necesarios para dividir el circuito.

Por que funciona

  • Cada gadget tiene un tamaño mínimo de estado de partición cuadrada ; es decir, una partición cuadrada mínima de ese gadget es de cierto tamaño.
  • Algunos dispositivos tienen varios estados con este tamaño; cada uno de estos estados son particiones cuadradas mínimas válidas .
  • Cuando los gadgets se combinan solo en las esquinas, la suma de los estados mínimos de partición cuadrada de los gadgets * sigue siendo el estado mínimo de partición cuadrada de la unión de ellos; puedes ver esto intuitivamente: unir en la esquina no le da suficiente espacio para que un cuadrado se expanda / conecte con un cuadrado de otro dispositivo.
  • Si bien la combinación de gadgets en la esquina no disminuye el tamaño total mínimo de la partición cuadrada , relaciona y restringe los gadgets entre sí.
  • Con las puertas que se muestran arriba, puede restringir los estados lo suficiente, de modo que si la fórmula lógica no es satisfactoria, entonces uno o más gadets tendrán que dividirse en cuadrados aún más pequeños y aumentar el tamaño mínimo de la partición cuadrada .

fuentes de gráficos

También puede ver imágenes más grandes eliminando los sufijos "s", "m", "l" de las URL de imgur. Por ejemplo, puede ver una imagen más grande de esto: http://i.stack.imgur.com/6CKlGs.jpg yendo a http://i.stack.imgur.com/6CKlG.jpg . Observe la "s" que falta antes de .jpg.

Ensalada Realz
fuente
3
Wow, eso es absolutamente impresionante. Desafortunadamente, no soy lo suficientemente inteligente como para verificar la reducción, pero confío en tu palabra :) ¡Gracias!
Erel Segal-Halevi
1
Entonces, la situación en mosaico es lo opuesto a la situación en el recubrimiento: en el recubrimiento, el recubrimiento cuadrado es polinomial y el recubrimiento rectangular es NP-duro, mientras que en el embaldosado, el recubrimiento cuadrado es NP-duro y el recubrimiento rectangular es polinomial.
Erel Segal-Halevi
8

NO(N3/2)

"Cubriendo polígonos ortogonales con cuadrados". LJ Aupperle y HE Conn y JM Keil y Joseph O'Rourke. Proc. 26a Allerton Conf. Commun. Control de Computación. , pp. 97-106, 1988. ( enlace para descargar el escaneo PDF )

Sin embargo, la cobertura resultante puede incluir cuadrados que se superponen. Está buscando un mosaico, donde los cuadrados no pueden solaparse, por lo que su problema no es el mismo.

Joseph O'Rourke
fuente
jajaja, estaba a la mitad de una formulación :(. ¡Muy interesante! Bienvenido a cs.SE.
Realz
2
Si entiendo correctamente, este documento permite que los cuadrados se superpongan (es decir, es un problema de cobertura). Estoy interesado en el caso en que los cuadrados no se superponen (es decir, es un problema de particionamiento / mosaico).
Erel Segal-Halevi
@ErelSegalHalevi: Oh, lo siento, no leí tu pregunta cuidadosamente.
Joseph O'Rourke el
2
Ah, entonces continuaré: D
Realz Slaw