Задача про складаний метр
Задача про складаний метр — це задача комбінаторної геометрії, яку можна сформулювати так:
Чи можна ланцюжок відрізків, що не перетинаються, перетворити неперервним рухом без перетинання відрізків так, що всі вершини ланцюжка (місця з'єднання відрізків) будуть лежати на одній прямій?
Тісно пов'язана задача — показати, що будь-який простий многокутник можна перетворити до опуклого вигляду безперервним перетворенням із збереженням під час руху довжин сторін, при цьому під час руху многокутник залишається простим[1].
Обидві задачі були успішно розв'язані групою Коннеллі, Демейн, Роут[2].
Історія[ред. | ред. код]
Задача, поставлена в 1970 році Сью Вайтсайдс[en], залишалася відкритою протягом 30 років. Попри позірну простоту, задача не має елементарного розв'язку.
Щоб зрозуміти тонкість питання, замість «складаного метра» розглянемо «шарнірний механізм, що реалізує граф-дерево». Не кожне таке дерево можна розпрямити. Так, у графа-павучка не можна розпрямити ноги, уникаючи самоперетинів і залишаючись у площині.
Цей павучок якийсь час надихав спроби математиків побудувати нерозпрямлюваний складаний метр — вони намагалися побудувати ламану, що двічі обходить контур павучка.
Комбінаторне доведення[ред. | ред. код]
Після виходу роботи Коннеллі та інших Ілеана Штрейну опублікувала спрощене комбінаторне доведення, сформульоване в термінології планування рухів руки робота. Як оригінальне доведення, так і доведення за Штрейну знаходять безперервний рух, за якого ніякі дві точки не рухаються назустріч одна одній. У версії доведення Штрейну до початкової форми додаються ребра для утворення неопуклої псевдотріангуляції, видаляється одне з доданих ребер опуклої оболонки цього графа і показується, що граф, який залишився, має однопараметричне сімейство рухів, у яких відстані не зменшуються. Якщо повторно застосовувати ці рухи, зрештою, вони призведуть до стану, в якому ніякий розширювальний рух не можливий, що буває, коли ланцюжок витягується в лінійку або многокутник стає опуклим.
Штрейну і Вітлі[3] навели застосування цього результату до математики оригамі — вони описали, як скласти будь-яке одновершинне оригамі, використовуючи тільки руху паперу без перетинів. По суті, цей процес складання є оберненою в часі версією задачі перетворення многокутника в опуклу форму, але на поверхні сфери, а не на евклідовій площині. Цей результат Паніна і Штрейну[4] розширили на сферичні многокутники з довжиною ребра, меншою 2π.
Узагальнення[ред. | ред. код]
Джон Пардон[5] узагальнив задачу про складний метр для спрямлюваних кривих. Він показав, що будь-яка спрямлювана жорданова крива може бути зроблена опуклою без збільшення довжини і без зменшення відстані між будь-якими двома точками кривої. За це дослідження, яке він виконав, ще будучи учнем середньої школи, Пардон отримав другу премію 2007 року в змаганні Intel Science Talent Search[en][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).