Введение
Продолжительное движение простого многоугольника к выпуклому виду. Задача о правиле столяра — это задача дискретной геометрии, которую можно сформулировать следующим образом: Возможно ли непрерывно переместить простой плоский многоугольник в положение, в котором все его вершины находятся в выпуклом положении, сохраняя при этом длины сторон и его простоту на протяжении всего движения? Тесно связанная задача заключается в доказательстве того, что любую несамопересекающуюся ломаную линию можно выпрямить, также с помощью непрерывного преобразования, сохраняющего расстояния между сторонами и избегающего пересечений. Задача получила свое название в честь многосоставных деревянных линеек, популярных среди плотников в XIX и начале XX веков, до того как усовершенствованные металлические рулетки сделали их устаревшими.
The carpenter's rule problem is a discrete geometry problem, which can be stated in the following manner: Can a simple planar polygon be moved continuously to a position where all its vertices are in convex position, so that the edge lengths and simplicity are preserved along the way? A closely related problem is to show that any non self crossing polygonal chain can be straightened, again by a continuous transformation that preserves edge distances and avoids crossings. Both problems were successfully solved by
The problem is named after the multiple jointed wooden rulers popular among carpenters in the 19th and early 20th centuries before improvements to metal tape measures made them obsolete.
Комбинаторное доказательство
Впоследствии Илеана Стрейну предложила упрощенное комбинаторное доказательство, сформулированное в терминах планирования движения роботизированной руки. И исходное доказательство, и доказательство Стрейну основаны на поиске нерасширяющих движений входных данных – непрерывных преобразований, при которых никакие две точки не сближаются. В версии доказательства Стрейну к входным данным добавляются ребра для формирования заостренной псевдотриангуляции, удаляется одно добавленное ребро выпуклой оболочки из этого графа, и показывается, что оставшийся граф имеет однопараметрическое семейство движений, в котором все расстояния не убывают. Повторное применение таких движений в конечном итоге приводит к состоянию, в котором дальнейшие расширяющие движения невозможны, что может произойти только тогда, когда входные данные были выпрямлены или сделаны выпуклыми. Авторы приводят применение этого результата к математике складывания бумаги, описывая, как сложить любую оригами-модель с одной вершиной, используя только простые, не самопересекающиеся движения бумаги. По сути, этот процесс складывания является обратным по времени к задаче выпуклости многоугольника длиной меньше π, но на поверхности сферы, а не в евклидовой плоскости. Этот результат был расширен на сферические многоугольники с длиной ребра меньше 2π.
Обобщение
обобщил проблему правила Карпентера на гладкие кривые. Он показал, что каждую гладкую кривую Жордана можно сделать выпуклой, не увеличивая её длину и не уменьшая расстояние между любой парой точек. Это исследование, выполненное ещё в школе, заняло второе место в конкурсе Intel Science Talent Search 2007 года.