211service.com
Origami vouwpatroonontwerp bewezen NP-hard
Zo'n 20 jaar of zo erkenden verschillende individuen dat het probleem van het vouwen van een vierkant vel papier in een willekeurige 3D-vorm veel overeenkomsten vertoonde met problemen in computationele geometrie. Deze beoefenaars begonnen algoritmen te ontwikkelen die automatisch de vouwpatronen genereren die een plat vel in een ingewikkelde vorm naar keuze veranderen. Dankzij dit en de magische kracht van moderne computermachines, ondergaat origami momenteel een technische en creatieve revolutie.
Maar deze nieuwe wetenschap van het vouwen van papier heeft geleid tot een aantal geheel nieuwe raadsels. Nadat origami een probleem van informatica was geworden, duurde het niet lang voordat origamisten zichzelf computerwetenschappelijke vragen begonnen te stellen. Ze willen vooral weten hoe rekenkundig moeilijk origami eigenlijk is. Vandaag hebben ze een antwoord dankzij het werk van Robert Lang , een van de wereldleiders in computationele origami, en een paar van zijn maatjes: Erik Morgen bij MIT, en Sándor Fekete aan de Technische Universiteit in Braunschweig, Duitsland.
Het proces van origami-ontwerp is conceptueel eenvoudig. Origamisten beginnen met de vorm die opnieuw moet worden gemaakt, bijvoorbeeld een spinvorm. Vervolgens tekenen ze dit opnieuw als een stokfiguur, in dit geval een lichaam en acht poten.
Origamisten weten dat elk uiteinde kan worden gereproduceerd door een flap papier op een bepaalde manier te vouwen. Dus de belangrijkste stap bij het ontwerpen van een origami-spin is het vinden van een manier om een stuk papier zo te vouwen dat het acht flappen van het juiste formaat en op afstand van elkaar produceert, één voor elke poot. Daarna is het gewoon een kwestie van de flappen zo vormgeven dat ze er beenvormig uitzien, een relatief eenvoudige taak.
De experts op dit gebied vermoeden al lang dat het proces van het veranderen van een stokfiguur in een vouwpatroon rekenkundig onhandelbaar is. Nu bewijzen Lang en co dat deze intuïtie juist is door aan te tonen dat het proces NP-hard is. Het is dus veel moeilijker om een vouwpatroon te bedenken dat een spin produceert dan om te controleren of een bepaalde oplossing correct is (dwz door het in een spin te vouwen).
Ze hebben dit gedaan met de standaardtruc om aan te tonen dat het probleem van origami gelijk is aan een ander probleem waarvan al bekend is dat het NP-moeilijk is, in dit geval het probleem van het inpakken van cirkels in een bepaalde ruimte.
Op het eerste gezicht is het moeilijk te zien hoe origami gerelateerd kan zijn aan het inpakken van cirkels, maar eigenlijk is er een duidelijke link. Denk terug aan het stokfiguur van de spin. Teken vervolgens een cirkel rond elk knooppunt met een straal die de helft is van de afstand tot een ander knooppunt. Het probleem van origami, het vinden van een manier om deze knooppunten zo te plaatsen dat het papier zo kan worden gevouwen dat elk knooppunt een hoekpunt in de uiteindelijke vorm vertegenwoordigt, staat dan gelijk aan het vinden van een optimale manier om de bollen te verpakken.
Hoewel het bewijs niet als een verrassing zal komen, heeft het wel een interessant gevolg. Tijdens het maken van deze doorbraak laten Lang en co zien dat elke reeks cirkels met een totale oppervlakte van 1 kan worden verpakt in een vierkant met de grootte 8/pi = 2,546... Een origami- sche triomf naar ieders maatstaven.
Referentie: arxiv.org/abs/1008.1224 : Cirkelverpakking voor origami-ontwerp is moeilijk