211service.com
Origami foldemønster-design bevist NP-hård
Omkring 20 år eller deromkring erkendte forskellige individer, at problemet med at folde et kvadratisk ark papir til en vilkårlig 3D-form havde mange ligheder med problemer inden for beregningsgeometri. Disse praktiserende læger begyndte at udvikle algoritmer, der automatisk genererer foldemønstrene, der gør et fladt ark til en indviklet form efter eget valg. Takket være dette og den magiske kraft i moderne computermaskiner gennemgår origami i øjeblikket en teknisk og kreativ revolution.
Men denne nye videnskab om papirfoldning har ført til nogle helt nye gåder. Efter at have forvandlet origami til et problem inden for datalogi, gik det ikke længe, før origamierne begyndte at stille sig selv datalogiske spørgsmål. De vil især gerne vide, hvor beregningsmæssigt svær origami faktisk er. I dag har de et svar takket være arbejdet med Robert Lang , en af verdens førende inden for computational origami, og et par af hans venner: Erik i morgen at MIT, and Sándor Fekete ved University of Technology i Braunschweig, Tyskland.
Processen med origami design er konceptuelt enkel. Origamister begynder med den form, der skal genskabes - siger en edderkopform. De tegner derefter dette som en pindefigur, der i dette tilfælde består af en krop og otte ben.
Origamister ved, at hver ekstremitet kan reproduceres ved at folde en papirklap på en bestemt måde. Så det vigtigste trin i at designe en origami-edderkop er at finde en måde at folde et stykke papir på, så det giver otte flapper i passende størrelse og med afstand, en til hvert ben. Herefter er det bare et spørgsmål om at forme flapperne, så de ser benformede ud, en forholdsvis ligetil opgave.
Eksperterne på dette område har længe haft mistanke om, at processen med at omdanne en pindefigur til et foldemønster er beregningsmæssigt vanskelig. Nu beviser Lang og co, at denne intuition er korrekt ved at vise, at processen er NP-hård. Så det er meget sværere at udtænke et foldemønster, der producerer en edderkop, end det er at kontrollere, at en given løsning er korrekt (dvs. ved at folde den til en edderkop).
De har gjort dette ved at bruge standardtricket med at vise, at problemet med origami svarer til et andet problem, der allerede er kendt for at være NP-hårdt, i dette tilfælde problemet med at pakke cirkler ind i et givet rum.
Ved første øjekast er det svært at se, hvordan origami kan relateres til cirkelpakning, men faktisk er der et ligetil link. Tænk tilbage på edderkoppens pindefigur. Tegn derefter en cirkel rundt om hver knude med en radius, der er halvdelen af afstanden til en anden knude. Problemet med origami, at finde en måde at placere disse noder på, så papiret kan foldes på en sådan måde, at hver node repræsenterer et toppunkt i den endelige form, svarer så til at finde en optimal måde at pakke kuglerne på.
Selvom beviset vil komme som en lille overraskelse, har det en interessant konsekvens. I løbet af dette gennembrud viser Lang og co, at ethvert sæt cirkler med et samlet areal på 1 kan pakkes ind i et kvadrat med størrelsen 8/pi = 2.546... En origamisk triumf efter enhvers standarder.
Ref: arxiv.org/abs/1008.1224 : Cirkelpakning til Origami Design er svær