Задача про складаний метр
Задача про складаний метр — це задача комбінаторної геометрії, яку можна сформулювати так:
Чи можна ланцюжок відрізків, що не перетинаються, перетворити неперервним рухом без перетинання відрізків так, що всі вершини ланцюжка (місця з'єднання відрізків) будуть лежати на одній прямій?
Тісно пов'язана задача — показати, що будь-який простий багатокутник може бути перетворений до опуклого вигляду безперервним перетворенням із збереженням під час руху довжин сторін, при цьому під час руху багатокутник залишається простим[1].
Обидві задачі були успішно розв'язані групою Коннеллі, Демейн, Роут[2].
Історія
Задача була поставлена в 1970 році Сью Вайтсайдс, і залишалася відкритою протягом 30 років. Незважаючи на позірну простоту, задача не має елементарного розв'язку.
Щоб зрозуміти тонкість питання, замість «складаного метра» розглянемо «шарнірний механізм, що реалізує граф-дерево». Не кожне таке дерево можна розпрямити. Так, у графу-павучка не можна розпрямити ноги, уникаючи самоперетинів і залишаючись у площині.
Цей павучок якийсь час надихав спроби математиків побудувати нерозпрямлюваний складаний метр — вони намагалися побудувати ламану, що двічі обходить контур павучка.
Комбінаторне доведення
Після виходу роботи Коннеллі та інших Ілеана Стрейну (Ileana Streinu) опублікувала спрощене комбінаторне доведення, сформульоване в термінології планування рухів руки робота. Як оригінальне доведення, так і доведення за Стрейну знаходять безперервний рух, за якого ніякі дві точки не рухаються назустріч одна одній. У версії доведення Стрейну до початкової форми додаються ребра для утворення неопуклої псевдотріангуляції, видаляється одне з доданих ребер опуклої оболонки цього графу і показується, що граф, який залишився, має однопараметричне сімейство рухів, у яких відстані не зменшуються. Якщо повторно застосовувати ці рухи, зрештою, вони призведуть до стану, в якому ніякий розширювальний рух не можливий, що буває, коли ланцюжок витягується в лінійку або багатокутник стає опуклим.
Стрейну і Вітлі[3] навели застосування цього результату до математики оригамі — вони описали, як скласти будь-яке одновершинне оригамі, використовуючи тільки руху паперу без перетинів. По суті, цей процес складання є оберненою в часі версією задачі перетворення багатокутника в опуклу форму, але на поверхні сфери, а не на евклідовій площині. Цей результат Паніна і Стрейну[4] розширили на сферичні багатокутники з довжиною ребра, меншою 2π.
Узагальнення
Джон Пардон[5] узагальнив задачу про складний метр для спрямлюваних кривих. Він показав, що будь-яка спрямлювана жорданова крива може бути зроблена опуклою без збільшення довжини і без зменшення відстані між будь-якими двома точками кривої. За це дослідження, яке він виконав, ще будучи учнем середньої школи, Пардон отримав другу премію 2007 року в змаганні Intel Science Talent Search[6].
Див. також
- Скорочувальний потік, неперервне перетворення замкнутої кривої на площині, яке зрештою приводить до опуклої кривої.
Примітки
- Простота багатокутника означає відсутність перетинів сторін.
- Connelly, Demaine, Rote, 2003.
- Streinu, Whiteley, 2005.
- Panina, Streinu, 2010.
- Pardon, 2009.
- Cunningham, 2007.
Література
- Панина Г.Ю. О шарнирных механизмах, пружинных графах и вывернутых наизнанку многогранниках. — 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:.. Попередня версія на 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:.
- John Pardon. On the unfolding of simple closed curves // Transactions of the American Mathematical Society. — 2009. — Т. 361, вип. 4. — С. 1749–1764. — DOI:..
- 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).