Меню
Главная
Случайная статья
Настройки
|
Задача о складном метре — это задача комбинаторной геометрии, которую можно сформулировать следующим образом:
Можно ли непересекающуюся цепочку отрезков преобразовать непрерывным движением без пересечения отрезков так, что все вершины цепочки (места сочленения отрезков) будут лежать на одной прямой?
Тесно связанная задача — показать, что любой простой многоугольник может быть преобразован к выпуклому виду непрерывным преобразованием с сохранением во время движения длин сторон, при этом во всё время движения многоугольник остаётся простым[1].
Обе задачи были успешно решены группой Коннелли, Демейн, Роте[2].
Содержание
История
Задача была поставлена в 1970 году Сью Уайтсайдс, и оставалась открытой в течение 30 лет. Несмотря на кажущуюся простоту, задача не имеет элементарного решения.
Чтобы понять тонкость вопроса, вместо «складного метра» рассмотрим «шарнирный механизм, реализующий граф-дерево». Не всякое такое дерево можно распрямить. Так, у графа-паучка нельзя распрямить ноги, избегая самопересечений и оставаясь в плоскости.
Этот паучок какое-то время вдохновлял попытки математиков построить нераспрямляемый складной метр — они пытались построить ломаную, дважды обходящую контур паучка.
Комбинаторное доказательство
После выхода работы Коннелли и др. Илеана Стрейну (Ileana Streinu) опубликовала упрощённое комбинаторное доказательство, сформулированное в терминологии планирования движений[англ.] руки робота. Как оригинальное доказательство, так и доказательство Стрейну находят непрерывное движение, при котором никакие две точки не двигаются навстречу друг другу. Версия Стрейну доказательства добавляет рёбра к исходной фигуре для образования невыпуклой псевдотриангуляции[англ.], удаляет одно добавленное ребро выпуклой оболочки этого графа и показывает, что оставшийся граф имеет однопараметрическое семейство движений, в которых расстояния не уменьшаются. Если повторно применять эти движения, в конечном счёте, они приведут к положению, в котором никакое расширяющее движение невозможно, что бывает, только когда цепочка вытягивается в линейку или многоугольник становится выпуклым.
Стрейну и Уитли[4] привели приложение этого результата к математике оригами — они описали, каким образом сложить любое одновершинное оригами, используя только непересекающиеся движения бумаги. По существу, этот процесс складывания является обращённой во времени версией задачи преобразования многоугольника в выпуклую форму, но на поверхности сферы, а не на евклидовой плоскости. Этот результат расширили Панина и Стрейну[5] на сферические многоугольники с длиной ребра, меньшей 2.
Обобщение
Джон Пардон[6] обобщил задачу о складном метре для спрямляемых кривых. Он показал, что любая спрямляемая жорданова кривая может быть сделана выпуклой без увеличения длины и без уменьшения расстояния между любыми двумя точками кривой. За это исследование, которое он сделал, ещё будучи студентом средней школы, Пардон получил вторую премию 2007 года в соревновании Intel Science Talent Search[англ.][7].
См. также- Укорачивающий поток, непрерывное преобразование замкнутой кривой на плоскости, в конце концов приводящее к выпуклой кривой.
Примечания
- Простота многоугольника означает отсутствие пересечений сторон.
- Connelly, Demaine, Rote, 2003.
- Рисунок примерный, показывает лишь идею нераспрямляемого графа. Чтобы на самом деле паучок не смог распрямить ноги, второе и третье колена должны быть чуть длиннее, но на рисунке они бы тогда слились.
- Streinu, Whiteley, 2005.
- Panina, Streinu, 2010.
- Pardon, 2009.
- Cunningham, 2007.
Литература- Панина Г.Ю. О шарнирных механизмах, пружинных графах и вывернутых наизнанку многогранниках. — 2008. Статья является заметками по лекции в Летней школе «Современная математика» , 2008
- Robert Connelly, Erik Demaine, Gnter 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..
|
|