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

Распрямление складного метра.

Задача о складном метре — это задача комбинаторной геометрии, которую можно сформулировать следующим образом:

Можно ли непересекающуюся цепочку отрезков преобразовать непрерывным движением без пересечения отрезков так, что все вершины цепочки (места сочленения отрезков) будут лежать на одной прямой?

Тесно связанная задача — показать, что любой простой многоугольник может быть преобразован к выпуклому виду непрерывным преобразованием с сохранением во время движения длин сторон, при этом во всё время движения многоугольник остаётся простым.

Обе задачи были успешно решены группой Коннелли, Демейн, Роте.

История

Паучок не может распрямить ноги, оставаясь в плоскости и избегая самопересечений.

Задача была поставлена в 1970 году Сью Уайтсайдс, и оставалась открытой в течение 30 лет. Несмотря на кажущуюся простоту, задача не имеет элементарного решения.

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

Этот паучок какое-то время вдохновлял попытки математиков построить нераспрямляемый складной метр — они пытались построить ломаную, дважды обходящую контур паучка.

Комбинаторное доказательство

После выхода работы Коннелли и др. Илеана Стрейну (Ileana Streinu) опубликовала упрощённое комбинаторное доказательство, сформулированное в терминологии планирования движений руки робота. Как оригинальное доказательство, так и доказательство Стрейну находят непрерывное движение, при котором никакие две точки не двигаются навстречу друг другу. Версия Стрейну доказательства добавляет рёбра к исходной фигуре для образования невыпуклой псевдотриангуляции, удаляет одно добавленное ребро выпуклой оболочки этого графа и показывает, что оставшийся граф имеет однопараметрическое семейство движений, в которых расстояния не уменьшаются. Если повторно применять эти движения, в конечном счёте, они приведут к положению, в котором никакое расширяющее движение невозможно, что бывает, только когда цепочка вытягивается в линейку или многоугольник становится выпуклым.

Стрейну и Уитли привели приложение этого результата к математике оригами — они описали, каким образом сложить любое одновершинное оригами, используя только непересекающиеся движения бумаги. По существу, этот процесс складывания является обращённой во времени версией задачи преобразования многоугольника в выпуклую форму, но на поверхности сферы, а не на евклидовой плоскости. Этот результат расширили Панина и Стрейну на сферические многоугольники с длиной ребра, меньшей 2π.

Обобщение

Джон Пардон обобщил задачу о складном метре для спрямляемых кривых. Он показал, что любая спрямляемая жорданова кривая может быть сделана выпуклой без увеличения длины и без уменьшения расстояния между любыми двумя точками кривой. За это исследование, которое он сделал, ещё будучи студентом средней школы, Пардон получил вторую премию 2007 года в соревновании Intel Science Talent Search.

См. также

• Укорачивающий поток, непрерывное преобразование замкнутой кривой на плоскости, в конце концов приводящее к выпуклой кривой.

Литература

• Панина Г.Ю. О шарнирных механизмах, пружинных графах и вывернутых наизнанку многогранниках. — 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. — doi:10.1016/j.comgeo.2010.04.002. — arXiv:1003.3490.
• 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).