В 1999 году студент Университета Уотерлу (University of Waterloo) Эрик Демейн (Erik Demaine) воплотил мечту любителей оригами — алгоритм, рассчитывающий, как сложить лист бумаги, чтобы получить любую трёхмерную фигуру. Но на практике он был практически бесполезен: алгоритму требовался очень длинный лист, получившиеся структуры состояли из кучи сгибов и были непрочными. Теперь Демейн научил своё детище выдавать реалистичные конструкции с минимальным количеством швов. Правда, пока у исследователя что-то не складывается…
«В 1999 мы доказали, что из бумаги можно сложить любой многогранник, но придуманный нами способ был крайне неэффективным, — объясняет Демейн. — Он работает, когда лист бумаги сверхдлинный и узкий. Но если вы начнёте с квадратного куска бумаги, старый алгоритм в конце концов сложит его в узкую полоску, истратив почти весь материал. Новый алгоритм обещает быть гораздо более эффективным. Это совершенно новая стратегия создания многогранников».Тот факт, что алгоритм сможет складывать фигуры с минимальным количеством швов, означает, что он сохранит «границы» листа. Представьте, что у вас есть круглый кусок бумаги, и вы хотите сложить из него стаканчик. Вы можете оставить небольшой кружок в центре плоским, а стороны загнуть гармошкой. В этом случае края стакана — это внешняя граница круга. Но ранняя версия алгоритма так не работала: стакан состоял бы из много раз свёрнутой тонкой полоски бумаги, и, вероятно, не мог бы удерживать воду.
«Новый алгоритм должен предлагать более практичные способы складывания листа, — рассказывает Демейн. — Мы не знаем, как оценить это математически, за исключением того, что на практике он, похоже, работает гораздо лучше. Однако одно математическое свойство всё-таки позволяет ясно различать два метода: в результате работы нового алгоритма граница листа бумаги совпадает с границей поверхности, которую вы пытаетесь получить. Мы называем это «водонепроницаемостью».У замкнутых поверхностей — например, у сферы — границ нет, поэтому при создании их оригами-версий, в тех местах, где границы листа встречаются, образуются швы. Алгоритм позволяет выбирать, где расположить эти швы. «Вы не можете получить полностью водонепроницаемую замкнутую поверхность, потому что где-то должны быть границы, но вы можете выбирать, куда их поместить».
Сложить нужную фигуру так, чтобы не оставалось лишнего материала — очень сложно: иногда для этого нужны десятки и сотни сгибов. Чтобы рассчитать, где должны располагаться эти сгибы, Демейн и его коллега Томохиро Тати (яп. 舘 知宏, англ. Tomohiro Tachi) использовали несколько методов, но главным стало построение диаграммы Вороного. Описать эту концепцию можно таким образом: представьте травянистую равнину, на которой одновременно зажгли несколько костров, причём огни распространяются по всем направлениям с одинаковой скоростью. Диаграмма Вороного описывает расположение костров и границы, где встречаются соседние огни. Эти границы и определяют места сгиба при работе нового алгоритма.
«Это очень впечатляюще, — говорит бывший инженер, а ныне оригамист Роберт Ланг (Robert Lang). Он назвал работу Демейна и Тати завершением двадцатилетнего квеста.Ланг также добавил, что его легко реализовать на практике. Уже известно, что алгоритм станет основой для следующей версии Origamizer — эта программа авторства Тати рассчитывает расположение сгибов для фигурок оригами. Вот в этом ролике Тати показывает её в действии:
«За это время мы видели, как разные учёные демонстрируют кусочки этого паззла: алгоритм, который складывает любую фигуру, но делает это не очень эффективно; алгоритм, который эффективно складывает определённые семейства древоподобных фигур, но не поверхности; алгоритм, складывающий деревья и поверхности, но не все фигуры. Новый алгоритм покрывает все эти возможности!»