Computational origami är en ny gren av datavetenskap studera effektiva algoritmer för att lösa pappersvikning problem. Detta fält började i huvudsak med Robert Langs arbete med algoritmisk origamidesign [25], med början omkring 1993. Sedan dess har fältet för beräknings origami vuxit betydligt. Syftet med denna rapport är att kartlägga arbetet inom området, med fokus på de senaste resultaten, och att presentera flera öppna problem som kvarstår. Undersökningen kan inte hoppas vara fullständig, men vi försöker täcka de flesta intresseområden. De flesta resultat i beräknings origami passar in i minst en av tre kategorier: universalitetsresultat, effektiva beslutsalgoritmer och beräkningsmässiga intractability resultat. Ett universalitetsresultat visar att allt, under en viss vikningsmodell, är möjligt. Till exempel kan varje trädformad origamibas (avsnitt 2.1), varje polygonal silhuett (avsnitt 2.3) och varje polyhedral yta (avsnitt 2.3) vikas av ett tillräckligt stort papper. Universalitet resultat kommer ofta med effektiva algoritmer för att hitta fällningar; ren existens resultat är sällsynta. När universalitetsresultaten är omöjliga (vissa objekt kan inte vikas), är det näst bästa resultatet en effektiv beslutsalgoritm för att avgöra om ett visst objekt kan vikas. Här betyder "effektiv" normalt "polynomtid". Till exempel finns det en polynom tid algoritm för att avgöra om en "karta" (grepp på veck markerade berg och dal) kan vikas med en sekvens av enkla veck (avsnitt 3.4). Inte alla pappersvikning problem har effektiva algoritmer, och detta kan bevisas av ett beräkningsbart intractability resultat. Till exempel är det NP-hård att avgöra om ett givet veck mönster viker in i någon platt origami (avsnitt 3.2), även när veck är begränsade till enkla veck (avsnitt 3.4). Dessa resultat innebär att det inte finns några polynom-tid algoritmer för dessa problem, om inte några av de svåraste beräkningsproblemen också kan lösas i polynom tid, vilket i allmänhet anses osannolikt. Vi skiljer ytterligare beräknings origami resultat som adresserar antingen origami design eller origami vikbarhet. I grund och botten, i origami design, vissa aspekter av målet konfiguration anges, och målet är att utforma en lämplig mål som kan vikas av papper. Om ja, varsågod.
Det finns ett rikt fält av arbete på origami design i matematik samhället1 REF ge en enkät.
Recent Results in Computational Origami
{'venue': 'Origami^{3}', 'journal': 'Origami^{3}', 'mag_field_of_study': ['Computer Science']}