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:
- Cubrir un polígono ortogonal con cuadrados, similar a mi problema, pero los cuadrados de cobertura se superponen. Este problema tiene una solución polinómica ( Aupperle, Conn, Keil y O'Rourke, 1988 ; Bar-Yehuda y Ben-Hanoch, 1996 ).
- Mosaico / descomposición / partición de un polígono ortogonal a rectángulos . Este problema tiene una solución polinómica ( Keil, 2000 ; Eppstein, 2009 ).
- Cubriendo un polígono ortogonal con rectángulos : se sabe que este problema es NP completo ( Culberson y Reckhow, 1988 ).
Estoy buscando un algoritmo para un mosaico mínimo con cuadrados .
algorithms
computational-geometry
tiling
Erel Segal-Halevi
fuente
fuente
Respuestas:
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 :
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.
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.FT F
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:
Ejemplo:
Así es como se usa:
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:
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".
Sin embargo, esto deja el caso sin restricciones:
Si combinamos dos cables i , podemos obtener una implicación bidireccional, esencialmente una igualdad booleana (in):
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 .
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.
Fotos :
Arriba: un cable .
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
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:
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:
puerta-valor-nombrado
Una puerta de valor con nombre es esencialmente un punto final como una puerta con un contacto de cable:
Odd -skip-gate : Odd omitiendo un cable
A veces es inconveniente tener solo cables de longitud impar. Por ejemplo:
Como puede ver, esa pequeña extensión es un poco molesta. Aquí hay una solución correspondiente, usando la puerta 4X3 :
Entonces, convirtiendo esto en una puerta, obtenemos la puerta de salto impar (en estructura metálica):
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:
Convéncete a ti mismo de que funciona:
La puerta se puede orientar según sea necesario.
puerta dividida : dividir un cable
División de un cable, estructura metálica:
Convénzase de que funciona:
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í:
Y una vista de los dos estados posibles:
La puerta se puede orientar según sea necesario.
cláusula-puerta
Para la cláusula-puerta , primero presentamos la cláusula-gadget :
Así es como se ve la puerta:
Explicación:
La puerta se puede orientar según sea necesario.
Reducción
Una ayuda visual (fuente original: Terrain Guarding es NP-Hard (PDF) , reproducido en tikz):
Luego:
Por que funciona
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
.fuente
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.
fuente