Задача о правиле Карпентера
— Задача правила плотника это задача дискретной геометрии , которую можно сформулировать следующим образом: можно ли простой плоский многоугольник непрерывно перемещать в положение, в котором все его вершины находятся в выпуклом положении , так, чтобы длины ребер и простота сохранялись вдоль линии способ? Тесно связанная проблема - показать, что любую несамопересекающуюся многоугольную цепь можно выпрямить, опять же с помощью непрерывного преобразования, которое сохраняет краевые расстояния и позволяет избежать пересечений.
Обе проблемы были успешно решены Коннелли, Демейн и Роте (2003) .
Проблема названа в честь многосоставных деревянных линеек, популярных среди плотников в 19 и начале 20 веков, прежде чем усовершенствования металлических рулеток сделали их устаревшими.
Комбинаторное доказательство
[ редактировать ]Впоследствии к своей работе Илеана Стрейну предоставила упрощенное комбинаторное доказательство, сформулированное в терминологии планирования движения руки робота . И исходное доказательство, и доказательство Стрейну основаны на поиске нерасширяющихся движений входных данных, непрерывных преобразований, при которых никакие две точки никогда не движутся навстречу друг другу. Версия доказательства Стрейну добавляет ребра к входным данным, чтобы сформировать заостренную псевдотриангуляцию , удаляет одно добавленное ребро выпуклой оболочки из этого графа и показывает, что оставшийся граф имеет однопараметрическое семейство движений, в котором все расстояния неубывают. Повторно применяя такие движения, можно в конечном итоге достичь состояния, в котором дальнейшие расширяющиеся движения невозможны, что может произойти только тогда, когда входные данные выпрямлены или выпуклы.
Стрейну и Уайтли (2005) применяют этот результат к математике складывания бумаги : они описывают, как сложить любую фигуру оригами с одной вершиной , используя только простые несамопересекающиеся движения бумаги. По сути, этот процесс складывания представляет собой обращенную во времени версию проблемы выпуклости многоугольника длиной меньше π, но на поверхности сферы, а не в евклидовой плоскости. Этот результат был расширен Паниной и Стрейну (2010) для сферических многоугольников с длиной ребра менее 2π.
Обобщение
[ редактировать ]Джон Пардон ( 2009 ) обобщил проблему правила Карпентера на спрямляемые кривые . Он показал, что любую спрямляемую жорданову кривую можно сделать выпуклой, не увеличивая ее длину и не уменьшая расстояния между любой парой точек. Это исследование, проведенное, когда он еще учился в старшей школе, заняло второе место в категории «Помилование» в конкурсе Intel Science Talent Search 2007 года ( Cunningham 2007 ).
См. также
[ редактировать ]- Поток, сокращающий кривую , непрерывное преобразование замкнутой кривой в плоскости, которое в конечном итоге делает ее выпуклой.
Ссылки
[ редактировать ]- Коннелли, Роберт ; Демейн, Эрик Д .; Роте, Гюнтер (2003), «Выпрямление многоугольных дуг и выпуклость многоугольных циклов» (PDF) , Дискретная и вычислительная геометрия , 30 (2): 205–239, doi : 10.1007/s00454-003-0006-7 , MR 1931840 . Предварительная версия появилась на 41-м ежегодном симпозиуме по основам информатики в 2000 году.
- Каннингем, Эйми (17 марта 2007 г.), «Следующее поколение», Science News : 166 .
- Стрейну, Илеана (2000), «Комбинаторный подход к планарному планированию движения руки робота без столкновений» , Труды 41-го ежегодного симпозиума по основам компьютерных наук , Компьютерное общество IEEE, стр. 443–453, doi : 10.1109/SFCS. 2000.892132 , МР 1931841 , S2CID 9420124
- Панина, Гаяне; Стрейну, Илеана (2010), «Сглаживание одновершинного оригами: нерасширяющийся случай», Вычислительная геометрия: теория и приложения , 43 (8): 678–687, arXiv : 1003.3490 , doi : 10.1016/j.comgeo.2010.04 .002 , МР 1931841
- Пардон, Джон (2009), «О развертывании простых замкнутых кривых», Transactions of the American Mathematical Society , 361 (4): 1749–1764, arXiv : 0809.1404 , doi : 10.1090/S0002-9947-08-04781-8 , МР 2465815 , S2CID 230031 .
- Стрейну, Илеана ; Уайтли, Уолтер (2005), «Оригами с одной вершиной и сферические расширяющиеся движения», Дискретная и вычислительная геометрия: Японская конференция, JCDCG 2004, Токио, Япония, 8–11 октября 2004 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 3742, Springer-Verlag, стр. 161–173, MR 2212105.