211service.com
Origami veckmönsterdesign Beprövad NP-hård
Ungefär 20 år eller så insåg olika individer att problemet med att vika ett fyrkantigt pappersark till en godtycklig 3D-form hade många likheter med problem inom beräkningsgeometri. Dessa utövare började utveckla algoritmer som automatiskt genererar veckmönster som förvandlar ett platt ark till en invecklad form som du väljer. Tack vare detta och den magiska kraften hos moderna datormaskiner genomgår origami för närvarande en teknisk och kreativ revolution.
Men denna nya vetenskap om pappersvikning har lett till några helt nya gåtor. Efter att ha förvandlat origami till ett problem inom datavetenskap, dröjde det inte länge innan origami började ställa sig datavetenskapliga frågor. I synnerhet vill de veta hur beräkningssvår origami faktiskt är. Idag har de ett svar tack vare arbetet med Robert Lang , en av världsledande inom datororigami, och ett par av hans kompisar: Erik imorgon vid MIT, och Sándor Fekete vid tekniska universitetet i Braunschweig, Tyskland.
Processen för origamidesign är konceptuellt enkel. Origamister börjar med formen som ska återskapas - säg en spindelform. De ritar sedan om detta till en käppfigur som i det här fallet består av en kropp och åtta ben.
Origamister vet att varje extremitet kan reproduceras genom att vika en flik av papper på ett speciellt sätt. Så nyckelsteget i att designa en origamispindel är att hitta ett sätt att vika ett papper så att det ger åtta flikar av lämplig storlek och åtskilda, en för varje ben. Efter det är det bara en fråga om att forma flikarna så att de ser benformade ut, en relativt enkel uppgift.
Experterna inom detta område har länge misstänkt att processen att förvandla en pinnefigur till ett veckmönster är beräkningsmässigt svårhanterlig. Nu bevisar Lang och co att denna intuition är korrekt genom att visa att processen är NP-hård. Så det är mycket svårare att skapa ett veckmönster som producerar en spindel än att kontrollera att en given lösning är korrekt (dvs. genom att vika den till en spindel).
De har gjort detta med standardtricket att visa att problemet med origami är likvärdigt med ett annat problem som redan är känt för att vara NP-hårt, i det här fallet problemet med att packa cirklar i ett givet utrymme.
Vid första anblicken är det svårt att se hur origami kan relateras till cirkelpackning, men det finns faktiskt en enkel länk. Tänk tillbaka på spindelns käppfigur. Rita sedan en cirkel runt varje nod med en radie som är halva avståndet till en annan nod. Problemet med origami, att hitta ett sätt att placera dessa noder så att papperet kan vikas på ett sådant sätt att varje nod representerar ett hörn i den slutliga formen, är då likvärdigt med att hitta ett optimalt sätt att packa sfärerna.
Även om beviset kommer som en liten överraskning, har det en intressant följd. Under loppet av detta genombrott visar Lang och co att vilken uppsättning cirklar som helst med en total yta på 1 kan packas i en kvadrat med storleken 8/pi = 2,546... En origamisk triumf enligt allas standarder.
Ref: arxiv.org/abs/1008.1224 : Circle Packing for Origami Design Is Hard