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