Embalaje de rectángulos en polígonos convexos pero sin rotaciones

23

Estoy interesado en el problema de empacar copias idénticas de rectángulos (2 dimensiones) en un polígono convexo (2 dimensiones) sin superposiciones. En mi problema, no puede rotar los rectángulos y puede suponer que están orientados en paralelo con los ejes. Solo se le dan las dimensiones de un rectángulo y los vértices del polígono y se le pregunta cuántas copias idénticas del rectángulo se pueden empaquetar en el polígono. Si se le permite rotar los rectángulos, creo que este problema es NP-duro. Sin embargo, ¿qué se sabe si no puede? ¿Qué tal si el polígono convexo es simplemente un triángulo? ¿Existen algoritmos de aproximación conocidos si el problema es NP-hard?

Resumen hasta el momento (21 de marzo '11). Peter Shor observa que podemos considerar este problema como uno de los cuadrados de unidades de empaque en un polígono convexo y que ese problema está en NP si impone un límite polinómico en el número de cuadrados / rectángulos que se empacarán. Sariel Har-Peled señala que hay un PTAS para el mismo caso polinomialmente delimitado. Sin embargo, en general, el número de cuadrados empaquetados puede ser exponencial en el tamaño de la entrada, que solo consiste en una lista posiblemente corta de pares de enteros. Las siguientes preguntas parecen estar abiertas.

¿Es la versión completa sin límites en NP? ¿Hay un PTAS para la versión ilimitada? ¿Es el caso delimitado polinomialmente en P o NPC? Y mi favorito personal, ¿es el problema más fácil si solo te limitas a empacar cuadrados de unidades en un triángulo?

Rafael
fuente
El embalaje con rectángulos 1x3 es NP-completo (con rotación) y supongo que se vuelve fácil si no permitimos las rotaciones. Usted encuentra el número máximo de rectángulos para cada fila (o columnas) y los agrega para obtener el número máximo total de rectángulos empaquetados.
Mohammad Al-Turkistany
No estoy seguro de que arreglar las dimensiones para que sean 1x3 (o cualquier otra cosa) ayuda demasiado para mi problema, ¿verdad? El polígono convexo no tiene necesariamente lados paralelos a los ejes y aún debe decidir dónde colocar los rectángulos. Puede colocarlos más abajo en el eje y primero y luego justificarlos a la izquierda como una heurística razonable, pero puede construir ejemplos con bastante facilidad donde esto no sea óptimo.
Raphael
99
Puedes aplicar una transformación afín para hacer todos los rectángulos. . Entonces el problema es equivalente al de empacar cuadrados. 1×1
Peter Shor
1
@turkistany: ¿Me darías una referencia que muestre la integridad de NP para los rectángulos 1x3? ¿O es fácil de observar?
Yoshio Okamoto
3
Al realizar una búsqueda basada en la observación de Peter Shor, aparece maven.smith.edu/~orourke/TOPP/P56.html , lo cual es interesante. Sin embargo, parece centrarse en polígonos simples generales (es decir, pueden ser cóncavos).
Raphael

Respuestas:

12

El problema puede reformularse como elegir un número máximo de puntos dentro de un polígono convexo, de modo que cada par de ellos esté a distancia (debajo de la métrica ) al menos 1 uno del otro (solo piense en los centros de los cuadrados) . Esto a su vez está relacionado con el mismo problema donde uno usa la distancia euclidiana regular. Esto, a su vez, está relacionado con el mallado, donde uno está interesado en dividir un polígono en regiones de buen comportamiento (es decir, toma el diagrama de Voronoi de los centros [ver Teselaciones Centroidales de Voronoi]).L1

De todos modos, una aproximación es bastante fácil. Desliza aleatoriamente una cuadrícula de longitud lateral O ( 1 / ϵ ) . Recorte el polígono en la cuadrícula y resuelva el problema dentro de cada pieza de intersección del polígono con la cuadrícula utilizando la fuerza bruta. Se debe seguir fácilmente un algoritmo con tiempo de ejecución O ( M n o i s e ( ϵ ) ) , donde M es el número de puntos (es decir, rectángulos) y(1ϵ)O(1/ϵ)O(Mnoise(ϵ))Mnoise(ϵ)es una función horrenda que depende solo de .ϵ

Sariel Har-Peled
fuente
Gracias. ¿Estoy en lo cierto al pensar que incluso en el caso en que tenemos un límite polinómico en el número de rectángulos / cuadrados, todavía no está claro si el problema está en P?
Raphael
1
Aquí están mis 2 centavos de adivinanzas / especulaciones ... Sería sorprendente si está en P: necesitaría mostrar algunas propiedades adicionales de la solución óptima. Sin embargo, supongo que una prueba formal de dureza NP está fuera de alcance: el problema tiene demasiada estructura. Feder y Greene demostraron que la agrupación del centro k es NP-difícil de aproximar dentro de un cierto factor. Creo / especulo que su prueba se puede utilizar para demostrar que el problema anterior es NP-Hard si el polígono tiene agujeros ...
Sariel Har-Peled
2

Estos dos documentos abordan su problema:

EG Birgin y RD Lobato, " Empaquetamiento ortogonal de rectángulos idénticos dentro de regiones convexas isotrópicas ", Computers & Industrial Engineering 59, pp. 595-602, 2010. 

EG Birgin, JM Martínez, FH Nishihara y DP Ronconi, " Empaque ortogonal de artículos rectangulares dentro de regiones convexas arbitrarias por optimización no lineal ", Computers & Operations Research 33, pp. 3535-3548, 2006.

 

Marcus Ritt
fuente
Estos documentos tratan de resolver el problema en la práctica. Hasta donde puedo decir, la pregunta es si se sabe que el problema es NP-hard.
András Salamon
3
Es bastante fácil mostrar que está en NP. Supongamos que le doy un diagrama del empaque óptimo que le dice qué cuadrados están tocando qué lados del polígono y qué cuadrados están arriba / abajo / izquierda / derecha de otros cuadrados. La cuestión de si puede encontrar las coordenadas para un conjunto de cuadrados que se empaquetan exactamente de esa manera es un programa lineal, por lo que puede verificar que este sea un diagrama para un empaque factible.
Peter Shor
44
Si todos los vértices de su polígono son enteros (o racionales), un resultado estándar en programas lineales dice que no necesita más que una cantidad polinómica de precisión adicional, y el programa lineal puede resolverse exactamente en tiempo polinómico. Disculpas si ya lo sabías, pero no puedo distinguir tu comentario anterior, e incluso si lo supieras, algunas personas no lo sabrán.
Peter Shor
2
Gracias. Lo supe una vez, pero fue bueno recordarlo. También parece que podría tener un número exponencial de cuadrados empaquetados en el polígono, por lo que no estoy seguro de que pueda darse el lujo de enumerarlos a todos. ¿Quizás hay algo de escala que puedes hacer para evitar esto?
Raphael
3
@Rafael: estaba suponiendo (sin justificación) que tenías un límite polinómico en el número de cuadrados. Si permite polígonos de tamaño exponencial, las cosas se vuelven mucho más complicadas.
Peter Shor
1

Peter Shor observó que al reescalar, este problema se convierte en empacar cuadrados unitarios en un polígono convexo.

Editar: el resto de esta respuesta no se aplica, ya que elimina el requisito explícitamente establecido de que las formas que se empaquetarán sean del mismo tamaño.


La pregunta relacionada NP-Hardness de un caso especial de problema de empaque ortogonal menciona un artículo con el resultado necesario para la primera pregunta:

  • Embalaje de cuadrados en un cuadrado, Joseph YT. Leung, Tommy W. Tam, CS Wong, Gilbert H. Young y Francis YL Chin, Journal of Parallel and Distributed Computing 10 271–275. ( enlace )

Del periódico:

Demostramos que el problema del empaque cuadrado es NP-completo al reducir el problema de 3 particiones.

Por lo tanto, el problema es NP-duro incluso para el caso especial donde los rectángulos a empacar son similares al contenedor. (A diferencia de los autores de este artículo, no estoy completamente convencido de que el problema esté en NP, ya que las posiciones pueden tener que especificarse con una gran precisión, lo que puede hacer que la verificación ya no sea polinómica en el tamaño de entrada. )

András Salamon
fuente
55
Mirando el papel, de los diagramas parece que los cuadrados que se van a empacar no son todos del mismo tamaño.
Peter Shor
1
@ Peter: Tienes razón, este documento no implica nada sobre el problema de Raphaël.
András Salamon
0

Quizás este documento pueda ser de su interés:

Mosaico de un polígono con rectángulos de Kenyon & Kenyon en FOCS 92.

Sylvain Peyronnet
fuente
Gracias. Sin embargo, si entiendo correctamente, un mosaico cubre exactamente el polígono. Esto casi nunca será posible en mi caso (considere un triángulo arbitrario en alguna orientación arbitraria) que parece hacer que mi problema de optimización sea fundamentalmente diferente.
Raphael
de hecho, este no es el mismo problema, mi error.
Sylvain Peyronnet
0

Si el polígono en el que desea empacar no es necesariamente convexo, entonces creo que el problema se vuelve NP-difícil. Aquí hay una prueba muy incompleta. La reducción es de algún problema de tipo Planar-3-SAT. Para cada variable puede tener un lugar de 1.1 x 1, dependiendo de dónde coloque un cuadrado en esta área determinará si su variable es verdadero o falso. Además, si deja .1 área a la izquierda / derecha, entonces puede mover otras dos casillas un poco más adentro, y también las que están detrás de ellas, eventualmente dando otro .1 espacio libre en otro lugar que ahora afecta a cuatro casillas y así sucesivamente. Después de tener tantas copias como las ocurrencias del literal respectivo, conecta estos tubos al componente de la cláusula respectiva y nuevamente utiliza un dispositivo similar para asegurarse de que de los tres tubos entrantes al menos uno tenga un espacio adicional .1.

domotorp
fuente
1
Esto suena plausible. Tenga en cuenta que Raphaël proporcionó un enlace en un comentario maven.smith.edu/~orourke/TOPP/P56.html con un puntero a un documento con la reducción real.
András Salamon
Oh, no me he dado cuenta, gracias.
domotorp