Origami Crease Pattern Design dimostrato NP-Hard

Circa 20 anni o giù di lì, vari individui hanno riconosciuto che il problema di piegare un foglio quadrato di carta in una forma 3D arbitraria aveva molte somiglianze con i problemi della geometria computazionale. Questi professionisti hanno iniziato a sviluppare algoritmi che generano automaticamente i modelli di piega che trasformano un foglio piatto in una forma intricata di tua scelta. Grazie a questo e al potere magico delle moderne macchine informatiche, l'origami sta attualmente attraversando una rivoluzione tecnica e creativa.

Ma questa nuova scienza della piegatura della carta ha portato ad alcuni enigmi completamente nuovi. Avendo trasformato gli origami in un problema di informatica, non passò molto tempo prima che gli origami iniziassero a porsi domande simili all'informatica. In particolare, vogliono sapere quanto sia effettivamente difficile dal punto di vista computazionale l'origami. Oggi hanno una risposta grazie al lavoro di Robert Lang , uno dei leader mondiali nell'origami computazionale, e un paio di suoi amici: Erik domani al MIT, e Sándor Fekete presso l'Università di tecnologia di Braunschweig, in Germania.

Il processo di progettazione dell'origami è concettualmente semplice. Gli origami iniziano con la forma da ricreare, ad esempio una forma di ragno. Quindi lo ridisegnano come una figura stilizzata composta, in questo caso, da un corpo e otto gambe.

Gli origamisti sanno che ogni estremità può essere riprodotta piegando un lembo di carta in un modo particolare. Quindi il passaggio chiave nella progettazione di un ragno origami è trovare un modo per piegare un pezzo di carta in modo che produca otto lembi, opportunamente dimensionati e distanziati, uno per ogni gamba. Dopodiché, si tratta solo di modellare i lembi per farli sembrare a forma di gamba, un compito relativamente semplice.

Gli esperti in questo campo hanno a lungo sospettato che il processo di trasformazione di una figura stilizzata in un modello di piega sia computazionalmente intrattabile. Ora Lang e co dimostrano che questa intuizione è corretta mostrando che il processo è NP-difficile. Quindi è molto più difficile ideare un modello di piega che produca un ragno piuttosto che verificare che una data soluzione sia corretta (cioè piegandola in un ragno).

Lo hanno fatto usando il trucco standard di mostrare che il problema degli origami è equivalente a un altro problema che è già noto per essere NP-difficile, in questo caso il problema di impacchettare i cerchi in un dato spazio.

A prima vista, è difficile vedere come l'origami possa essere correlato all'imballaggio circolare, ma in realtà c'è un collegamento semplice. Ripensa alla figura stilizzata del ragno. Quindi disegna un cerchio attorno a ciascun nodo con un raggio che è metà della distanza da un altro nodo. Il problema dell'origami, trovare un modo per posizionare questi nodi in modo che la carta possa essere piegata in modo tale che ogni nodo rappresenti un vertice nella forma finale, equivale quindi a trovare un modo ottimale per impacchettare le sfere.

Anche se la prova sarà una piccola sorpresa, ha un interessante corollario. Nel fare questo passo avanti, Lang e colleghi mostrano che qualsiasi insieme di cerchi con un'area totale di 1 può essere compresso in un quadrato di dimensione 8/pi = 2,546... Un trionfo origamico per gli standard di chiunque.

Rif: arxiv.org/abs/1008.1224 : L'imballaggio circolare per la progettazione di origami è difficile

nascondere