Problém tesařů - Carpenters rule problem - Wikipedia
The problém s tesařským pravidlem je diskrétní geometrie problém, který lze konstatovat následujícím způsobem: Může a jednoduchý rovinný mnohoúhelník být nepřetržitě přesouván do polohy, kde jsou všechny jeho vrcholy konvexní pozice, aby byly podélně zachovány délky hran a jednoduchost? Úzce souvisejícím problémem je ukázat, že každý nepřekračuje sám sebe polygonální řetěz lze narovnat, opět kontinuální transformací, která zachovává vzdálenosti od hran a vyhýbá se křížení.
Oba problémy byly úspěšně vyřešeny Connelly, Demaine & Rote (2003).
Kombinatorický důkaz
Následně po jejich práci Ileana Streinu poskytl zjednodušený kombinatorický důkaz formulovaný v terminologii robotického ramene plánování pohybu. Jak původní důkaz, tak Streinuův důkaz fungují tak, že nacházejí neexpanzivní pohyby vstupu, kontinuální transformace tak, že žádné dva body se nikdy nepřiblíží k sobě. Streinova verze důkazu přidává hrany ke vstupu a tvoří a špičatá pseudotriangulace, odstraní z tohoto grafu jednu přidanou konvexní hranu trupu a ukazuje, že zbývající graf má jednoparametrovou rodinu pohybů, ve kterých všechny vzdálenosti neklesají. Opakovaným používáním takových pohybů se člověk nakonec dostane do stavu, ve kterém již nejsou možné žádné další expanzivní pohyby, ke kterým může dojít pouze tehdy, když je vstup narovnán nebo konvexován.
Streinu & Whiteley (2005) poskytnout aplikaci tohoto výsledku matematika skládání papíru: popisují, jak složit libovolný vrchol origami tvar používající pouze jednoduché nesekující se pohyby papíru. V podstatě je tento skládací proces časově obrácenou verzí problému konvexifikace polygonu délky menší než π, ale spíše na povrchu koule než v euklidovské rovině. Tento výsledek byl rozšířen o Panina a Streinu (2010) pro sférické polygony o délce hrany menší než 2π.
Zobecnění
John Pardon (2009 ) zobecnil problém Tesařova pravidla na usměrnitelné křivky. Ukázal, že každý napravitelný Jordanova křivka může být konvexní, aniž by se zvětšila jeho délka a aniž by se zmenšila vzdálenost mezi jakoukoli dvojicí bodů. Tento výzkum, který byl proveden ještě jako student střední školy, získal v roce 2007 pro Pardon druhé místo Vyhledávání talentů Intel Science (Cunningham 2007 ).
Viz také
- Průběh zkrácení křivky, kontinuální transformace uzavřené křivky v rovině, která ji nakonec konvexifikuje
Reference
- Connelly, Robert; Demaine, Erik D.; Rote, Günter (2003), "Rovnání polygonálních oblouků a konvexikační polygonální cykly" (PDF), Diskrétní a výpočetní geometrie, 30 (2): 205–239, doi:10.1007 / s00454-003-0006-7, PAN 1931840. Předběžná verze se objevila na 41. výroční sympozium o základech informatiky, 2000.
- Cunningham, Aimee (17. března 2007), „Nová generace“, Vědecké zprávy: 166.
- Streinu, Ileana (2000), „Kombinatorický přístup k plánování pohybu nekolidujících robotických ramen“, Sborník 41. výročního sympozia o základech informatiky, IEEE Computer Society, str. 443–453, doi:10.1109 / SFCS.2000.892132, PAN 1931841
- Panina, Gaiane; Streinu, Ileana (2010), „Flattinging single-vertex origami: The non-expanans case“, Výpočetní geometrie: Teorie a aplikace, 43 (8): 678–687, arXiv:1003.3490, doi:10.1016 / j.comgeo.2010.04.002, PAN 1931841
- Pardon, Johne (2009), „O vývoji jednoduchých uzavřených křivek“, Transakce Americké matematické společnosti, 361 (4): 1749–1764, arXiv:0809.1404, doi:10.1090 / S0002-9947-08-04781-8, PAN 2465815.
- Streinu, Ileana; Whiteley, Walter (2005), „Origami s jedním vrcholem a sférické expanzivní pohyby“, Diskrétní a výpočetní geometrie: Japonská konference, JCDCG 2004, Tokio, Japonsko, 8. – 11. Října 2004, revidované vybrané příspěvky, Přednášky v informatice, 3742, Springer-Verlag, str. 161–173, PAN 2212105