Diseño de patrón de pliegue de origami probado NP-Hard

Aproximadamente unos 20 años, varias personas reconocieron que el problema de doblar una hoja de papel cuadrada en una forma tridimensional arbitraria tenía muchas similitudes con los problemas de geometría computacional. Estos profesionales comenzaron a desarrollar algoritmos que generan automáticamente los patrones de pliegue que convierten una hoja plana en una forma intrincada de su elección. Gracias a esto y al poder mágico de las máquinas informáticas modernas, el origami está experimentando actualmente una revolución técnica y creativa.

Pero esta nueva ciencia del plegado de papel ha dado lugar a algunos enigmas completamente nuevos. Habiendo convertido el origami en un problema de la informática, no pasó mucho tiempo antes de que los origamistas comenzaran a hacerse preguntas similares a las de la informática. En particular, quieren saber cuán computacionalmente difícil es realmente el origami. Hoy tienen respuesta gracias al trabajo de Robert Lang , uno de los líderes mundiales en origami computacional, y un par de sus amigos: Erik mañana en el MIT, y Sándor Fekete en la Universidad de Tecnología de Braunschweig, Alemania.

El proceso de diseño de origami es conceptualmente simple. Los origamistas comienzan con la forma que se va a recrear, por ejemplo, una forma de araña. Luego lo vuelven a dibujar como una figura de palo que consta, en este caso, de un cuerpo y ocho piernas.

Los origamistas saben que cada extremidad se puede reproducir doblando una solapa de papel de una manera particular. Entonces, el paso clave en el diseño de una araña de origami es encontrar una manera de doblar una hoja de papel de manera que produzca ocho solapas espaciadas y de tamaño adecuado, una para cada pata. Después de eso, es solo una cuestión de dar forma a las solapas para que parezcan en forma de pierna, una tarea relativamente sencilla.

Los expertos en este campo han sospechado durante mucho tiempo que el proceso de convertir una figura de palo en un patrón de pliegue es computacionalmente intratable. Ahora, Lang y sus colegas demuestran que esta intuición es correcta al demostrar que el proceso es NP-difícil. Por lo tanto, es mucho más difícil diseñar un patrón de pliegue que produzca una araña que verificar que una solución dada sea correcta (es decir, doblándola en una araña).

Lo han hecho utilizando el truco estándar de mostrar que el problema del origami es equivalente a otro problema que ya se sabe que es NP-hard, en este caso, el problema de empaquetar círculos en un espacio dado.

A primera vista, es difícil ver cómo el origami se puede relacionar con el empaquetado circular, pero en realidad hay un vínculo sencillo. Piense en la figura de palo de la araña. Luego dibuja un círculo alrededor de cada nodo con un radio que sea la mitad de la distancia a otro nodo. El problema del origami, encontrar una forma de posicionar estos nodos para que el papel se pueda doblar de tal manera que cada nodo represente un vértice en la forma final, equivale entonces a encontrar una forma óptima de empaquetar las esferas.

Si bien la prueba será una pequeña sorpresa, tiene un corolario interesante. En el curso de hacer este gran avance, Lang y sus colegas demostraron que cualquier conjunto de círculos con un área total de 1 se puede empaquetar en un cuadrado de tamaño 8 / pi = 2.546 ... Un triunfo del origamic para los estándares de cualquiera.

Ref: arxiv.org/abs/1008.1224 : Empacar en círculos para el diseño de origami es difícil

esconder