Conception de motif de pli en origami prouvée NP-dur

Une vingtaine d'années environ, diverses personnes ont reconnu que le problème du pliage d'une feuille de papier carrée en une forme 3D arbitraire présentait de nombreuses similitudes avec les problèmes de géométrie informatique. Ces praticiens ont commencé à développer des algorithmes qui génèrent automatiquement les motifs de plis qui transforment un drap plat en une forme complexe de votre choix. Grâce à cela et à la puissance magique des machines informatiques modernes, l'origami connaît actuellement une révolution technique et créative.

Mais cette nouvelle science du pliage du papier a conduit à des énigmes entièrement nouvelles. Ayant fait de l'origami un problème d'informatique, il ne fallut pas longtemps avant que les origamistes commencent à se poser des questions de type informatique. En particulier, ils veulent savoir à quel point l'origami est difficile en termes de calcul. Aujourd'hui, ils ont une réponse grâce au travail de Robert Lang , l'un des leaders mondiaux de l'origami informatique, et quelques-uns de ses amis : Erik Demaine au MIT, et Sandor Fekete à l'Université de Technologie de Braunschweig, en Allemagne.

Le processus de conception de l'origami est conceptuellement simple. Les origamistes commencent par la forme à recréer, disons une forme d'araignée. Ils le redessinent ensuite sous la forme d'un bâton composé, dans ce cas, d'un corps et de huit jambes.

Les origamistes savent que chaque extrémité peut être reproduite en pliant un rabat de papier d'une manière particulière. Ainsi, l'étape clé dans la conception d'une araignée en origami est de trouver un moyen de plier un morceau de papier de manière à produire huit rabats de taille et d'espacement appropriés, un pour chaque jambe. Après cela, il s'agit simplement de façonner les rabats pour leur donner l'apparence d'une jambe, une tâche relativement simple.

Les experts dans ce domaine soupçonnent depuis longtemps que le processus de transformation d'un bonhomme allumette en un motif de pli est insoluble du point de vue informatique. Lang et co prouvent maintenant que cette intuition est correcte en montrant que le processus est NP-difficile. Il est donc beaucoup plus difficile de concevoir un motif de pli qui produit une araignée que de vérifier qu'une solution donnée est correcte (c'est-à-dire en la pliant en une araignée).

Ils l'ont fait en utilisant l'astuce standard consistant à montrer que le problème de l'origami est équivalent à un autre problème qui est déjà connu pour être NP-difficile, dans ce cas le problème de l'emballage de cercles dans un espace donné.

À première vue, il est difficile de voir comment l'origami peut être lié à l'emballage en cercle, mais en réalité, il existe un lien simple. Pensez à la figure de bâton de l'araignée. Ensuite, dessinez un cercle autour de chaque nœud avec un rayon qui est la moitié de la distance à un autre nœud. Le problème de l'origami, trouver un moyen de positionner ces nœuds pour que le papier puisse être plié de telle sorte que chaque nœud représente un sommet dans la forme finale, revient alors à trouver une manière optimale d'emballer les sphères.

Bien que la preuve ne surprenne pas, elle a un corollaire intéressant. Au cours de cette percée, Lang et ses collègues montrent que n'importe quel ensemble de cercles d'une aire totale de 1 peut être emballé dans un carré de taille 8/pi = 2,546… Un triomphe origamique selon les normes de quiconque.

Réf : arxiv.org/abs/1008.1224 : L'emballage en cercle pour la conception d'origami est difficile

cacher