Задача про складаний метр

Задача про складаний метр — це задача комбінаторної геометрії, яку можна сформулювати так:

Чи можна ланцюжок відрізків, що не перетинаються, перетворити неперервним рухом без перетинання відрізків так, що всі вершини ланцюжка (місця з'єднання відрізків) будуть лежати на одній прямій?

Тісно пов'язана задача — показати, що будь-який простий многокутник можна перетворити до опуклого вигляду безперервним перетворенням із збереженням під час руху довжин сторін, при цьому під час руху многокутник залишається простим^[1].

Обидві задачі були успішно розв'язані групою Коннеллі, Демейн, Роут^[2].

Задача, поставлена в 1970 році Сью Вайтсайдс^[en], залишалася відкритою протягом 30 років. Попри позірну простоту, задача не має елементарного розв'язку.

Щоб зрозуміти тонкість питання, замість «складаного метра» розглянемо «шарнірний механізм, що реалізує граф-дерево». Не кожне таке дерево можна розпрямити. Так, у графа-павучка не можна розпрямити ноги, уникаючи самоперетинів і залишаючись у площині.

Цей павучок якийсь час надихав спроби математиків побудувати нерозпрямлюваний складаний метр — вони намагалися побудувати ламану, що двічі обходить контур павучка.

Після виходу роботи Коннеллі та інших Ілеана Штрейну опублікувала спрощене комбінаторне доведення, сформульоване в термінології планування рухів руки робота. Як оригінальне доведення, так і доведення за Штрейну знаходять безперервний рух, за якого ніякі дві точки не рухаються назустріч одна одній. У версії доведення Штрейну до початкової форми додаються ребра для утворення неопуклої псевдотріангуляції, видаляється одне з доданих ребер опуклої оболонки цього графа і показується, що граф, який залишився, має однопараметричне сімейство рухів, у яких відстані не зменшуються. Якщо повторно застосовувати ці рухи, зрештою, вони призведуть до стану, в якому ніякий розширювальний рух не можливий, що буває, коли ланцюжок витягується в лінійку або многокутник стає опуклим.

Штрейну і Вітлі^[3] навели застосування цього результату до математики оригамі — вони описали, як скласти будь-яке одновершинне оригамі, використовуючи тільки руху паперу без перетинів. По суті, цей процес складання є оберненою в часі версією задачі перетворення многокутника в опуклу форму, але на поверхні сфери, а не на евклідовій площині. Цей результат Паніна і Штрейну^[4] розширили на сферичні многокутники з довжиною ребра, меншою 2π.

Джон Пардон^[5] узагальнив задачу про складний метр для спрямлюваних кривих. Він показав, що будь-яка спрямлювана жорданова крива може бути зроблена опуклою без збільшення довжини і без зменшення відстані між будь-якими двома точками кривої. За це дослідження, яке він виконав, ще будучи учнем середньої школи, Пардон отримав другу премію 2007 року в змаганні Intel Science Talent Search^[en][6].

• Вкорочувальний потік, неперервне перетворення замкнутої кривої на площині, яке зрештою приводить до опуклої кривої.

• Панина Г.Ю. О шарнирных механизмах, пружинных графах и вывернутых наизнанку многогранниках. — 2008. Стаття є замітками за лекцією в Літній школі «Сучасна математика» , 2008
• Robert Connelly, Erik Demaine, Günter Rote. Straightening polygonal arcs and convexifying polygonal cycles // Discrete and Computational Geometry. — 2003. — Т. 30, вип. 2. — С. 205–239. — DOI:10.1007/s00454-003-0006-7.. Попередня версія на 41-ому щорічному симпозіумі Foundations of Computer Science, 2000.
• Aimee Cunningham. The Next Generation // Science News. — 2007. — С. 166..
• Ileana Streinu. Proceedings of the 41st Annual Symposium on Foundations of Computer Science. — IEEE Computer Society, 2000. — С. 443–453. — doi:10.1109/SFCS.2000.892132.
• Gaiane Panina, Ileana Streinu. Flattening single-vertex origami: The non-expansive case // Computational Geometry: Theory and Applications. — 2010. — Т. 43, вип. 8. — С. 678–687. — arXiv:1003.3490. — DOI:10.1016/j.comgeo.2010.04.002.
• John Pardon. On the unfolding of simple closed curves // Transactions of the American Mathematical Society. — 2009. — Т. 361, вип. 4. — С. 1749–1764. — DOI:10.1090/S0002-9947-08-04781-8..
• Ileana Streinu, Walter Whiteley. Discrete and Computational Geometry: Japanese Conference, JCDCG 2004, Tokyo, Japan, October 8-11, 2004, Revised Selected Papers. — Springer-Verlag, 2005. — Т. 3742. — С. 161–173. — (Lecture Notes in Computer Science).