В 1999 году Эрик Демейн (Erik Demaine), тогда еще 18-летний аспирант Университета Уотерлу в Канаде описал алгоритм, который мог бы определить, как свернуть лист бумаги в любую мыслимую трехмерную форму. Это была значимая веха в области вычислительных оригами, но алгоритм не мог создать схемы для складывания, которые можно было бы действительно применить на практике.

По существу, алгоритм брал за основу очень длинную полоску бумаги и сворачивал ее в желаемую форму. Полученные структуры, как правило, имели много линий швов, где слои бумажной ленты накладывались друг на друга, образуя складки, из-за чего получаемые конструкции были не очень прочными.

В 1999 году Демейн доказал, что можно сложить любой полиэдр, но способ, которым этого можно достичь, оказался не самым эффективным. Предложенный метод работает, если исходный лист бумаги длинный и узкий. Но если нужно работать, например, с квадратным листом, то алгоритм все равно будет сначала складывать бумагу до тонкой полосы, растрачивая весь материал почем зря.

Теперь профессор электротехники и информатики Массачусетского технологического института Эрик Демейн и его коллега Томохиро Тачи из Токийского университета готовы объявить о завершении квеста, который начался с работы 1999 года: в июле 2017 года на симпозиуме по вычислительной геометрии они представят алгоритм для создания оригами, который гарантирует минимально возможное количество швов. Демейн и Тачи также работают над внедрением алгоритма в новой версии Origamizer — бесплатного ПО для генерации рисунков с оригами. Первая версия была выпущена Тачи в 2008 году. Читать дальше →

https://habr.com/post/373571/?utm_campaign=373571