Problem reguły stolarskiej
Zagadnienie reguły cieśli jest problemem geometrii dyskretnej , które można sformułować w następujący sposób: Czy prosty płaski wielokąt można przesuwać w sposób ciągły do pozycji, w której wszystkie jego wierzchołki są w pozycji wypukłej , tak aby długość krawędzi i prostota były zachowane wzdłuż sposób? Ściśle powiązanym problemem jest pokazanie, że każdy łańcuch wielokątny, który nie przecina się samoczynnie , można wyprostować, ponownie przez ciągłą transformację, która zachowuje odległości krawędzi i unika skrzyżowań.
Oba problemy zostały pomyślnie rozwiązane przez Connelly, Demaine & Rote (2003) .
Dowód kombinatoryczny
W następstwie ich pracy Ileana Streinu przedstawiła uproszczony dowód kombinatoryczny sformułowany w terminologii planowania ruchu ramienia robota . Zarówno oryginalny dowód, jak i dowód Streinu polegają na znalezieniu nieekspansywnych ruchów wejścia, ciągłych transformacji, takich że żadne dwa punkty nigdy nie zbliżają się do siebie. Wersja dowodu Streinu dodaje krawędzie do danych wejściowych, tworząc spiczastą pseudotriangulację , usuwa jedną dodaną wypukłą krawędź kadłuba z tego wykresu i pokazuje, że pozostały wykres ma jednoparametrową rodzinę ruchów, w których wszystkie odległości nie maleją. Wielokrotne stosowanie takich ruchów prowadzi ostatecznie do stanu, w którym dalsze ruchy ekspansywne nie są możliwe, co może nastąpić tylko wtedy, gdy dane wejściowe zostaną wyprostowane lub wypukłe.
Streinu i Whiteley (2005) przedstawiają zastosowanie tego wyniku do matematyki składania papieru : opisują, jak złożyć dowolny kształt origami z jednym wierzchołkiem , używając tylko prostych, nie przecinających się ruchów papieru. Zasadniczo ten proces składania jest odwróconą w czasie wersją problemu wypukłości wielokąta o długości mniejszej niż π, ale na powierzchni kuli, a nie na płaszczyźnie euklidesowej. Wynik ten został rozszerzony przez Paninę i Streinu (2010) dla sferycznych wielokątów o długości krawędzi mniejszej niż 2π.
Uogólnienie
John Pardon ( 2009 ) uogólnił problem reguły Carpentera na prostowalne krzywe . Pokazał, że każdą prostowalną krzywą Jordana można uczynić wypukłą bez zwiększania jej długości i bez zmniejszania odległości między dowolną parą punktów. Badania te, przeprowadzone, gdy był jeszcze uczniem szkoły średniej, zdobyły drugie miejsce za Pardon w 2007 Intel Science Talent Search ( Cunningham 2007 ).
Zobacz też
- Przepływ skracający krzywą , ciągła transformacja zamkniętej krzywej w płaszczyźnie, która ostatecznie ją wypukła
- Connelly, Robert ; Demaine, Erik D .; Rote, Günter (2003), „Prostowanie łuków wielokątnych i wypukłe cykle wielokątne” (PDF) , Discrete and Computational Geometry , 30 (2): 205–239, doi : 10.1007 / s00454-003-0006-7 , MR 1931840 . Wstępna wersja pojawiła się na 41. dorocznym sympozjum na temat podstaw informatyki w 2000 r.
- Cunningham, Aimee (17 marca 2007), „Następna generacja”, Science News : 166 .
- Streinu, Ileana (2000), „Kombinatoryczne podejście do planarnego, niekolizyjnego planowania ruchu ramienia robota” , Proceedings of the 41. Annual Symposium on Foundations of Computer Science , IEEE Computer Society, s. 443–453, doi : 10.1109/SFCS. 2000.892132 , MR 1931841 , S2CID 9420124
- Panina, Gaiane; Streinu, Ileana (2010), „Spłaszczanie origami z jednym wierzchołkiem: przypadek nieekspansywny”, Geometria obliczeniowa: teoria i zastosowania , 43 (8): 678–687, arXiv : 1003,3490 , doi : 10.1016/j.comgeo.2010.04 0,002 , MR 1931841
- Pardon, John (2009), „O rozwijaniu prostych krzywych zamkniętych”, Transactions of the American Mathematical Society , 361 (4): 1749–1764, arXiv : 0809,1404 , doi : 10.1090/S0002-9947-08-04781-8 , MR 2465815 , S2CID 230031 .
- Streinu, Ileana ; Whiteley, Walter (2005), „Single-vertex origami and spherical ekspansywne ruchy”, Discrete and Computational Geometry: Japanese Conference, JCDCG 2004, Tokio, Japonia, 8-11 października 2004, Revised Selected Papers, Lecture Notes in Computer Science, tom. 3742, Springer-Verlag, s. 161–173, MR 2212105