Новый алгоритм создает схемы оригами для любых трехмерных объектов

Инженер и специалист в области компьютерных наук из Массачусетского технологического института (MIT) завершил начатую почти 20 лет назад работу по созданию алгоритма, способного составлять схемы оригами для трехмерных объектов. О результате он расскажет на Конференции по вычислительной геометрии, которая пройдет в июле в Брисбане. Подробнее об алгоритме можно прочитать на сайте института. В своей работе 1999 года Эрик Демейн, сейчас профессор MIT, а на тот момент студент Университета Ватерлоо, описал алгоритм, который мог указать, как сложить лист бумаги в трехмерную форму. Хотя это была заметная работа, на тот момент она не имела практического применения: алгоритм требовал длинной полосы бумаги и складывал ее далеко не самым эффективным способом. «В 1999 году мы доказали, что можно сложить любой многогранник, но способ был очень неэффективным. Он был хорош, если у вас был супердлинный и узкий лист бумаги. Но если вы собирались начать с квадратного листа, но старый алгоритм сначала сложил бы его в узкую полосу, теряя почти весь материал», – объяснил Демейн. В анонсе своего выступления на конференции Демейн со своим соавтором Томохиро Тати объявили о создании алгоритма, дающего схему любого многогранника (обеъмного объекта с плоскими гранями) с наименьшим количеством сгибов. Преобразовать реальный объект в многогранник несложно с помощью компьютерных программ. Работа программы начинается с размещения граней объекта на плоскости, при этом соприкасающиеся грани могут оказаться далеко друг от друга. В результате сложной задачей становится рассчитать сгибы, нужные, чтобы избавиться от лишней бумаги между такими близкими гранями. Для решения этой задачи авторы алгоритма использовали диаграмму (или разбиение) Вороного, предложенную российским математиком Георгием Вороным. Она позволяет разделить плоскость на участки, каждая точка которых ближе всего к находящемуся на ней «центру», чем к любому другому.