Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Задача про складаний метр це задача комбінаторної геометрії яку можна сформулювати так Чи можна ланцюжок відрізків що не

Задача про складаний метр

Задача про складаний метр

Задача про складаний метр — це задача комбінаторної геометрії, яку можна сформулювати так:

Чи можна ланцюжок відрізків, що не перетинаються, перетворити неперервним рухом без перетинання відрізків так, що всі вершини ланцюжка (місця з'єднання відрізків) будуть лежати на одній прямій?

Тісно пов'язана задача — показати, що будь-який простий многокутник можна перетворити до опуклого вигляду безперервним перетворенням із збереженням під час руху довжин сторін, при цьому під час руху многокутник залишається простим.

Обидві задачі були успішно розв'язані групою Коннеллі, Демейн, Роут.

Історія

Задача, поставлена в 1970 році [en], залишалася відкритою протягом 30 років. Попри позірну простоту, задача не має елементарного розв'язку.

Щоб зрозуміти тонкість питання, замість «складаного метра» розглянемо «шарнірний механізм, що реалізує граф-дерево». Не кожне таке дерево можна розпрямити. Так, у графа-павучка не можна розпрямити ноги, уникаючи самоперетинів і залишаючись у площині.

Цей павучок якийсь час надихав спроби математиків побудувати нерозпрямлюваний складаний метр — вони намагалися побудувати ламану, що двічі обходить контур павучка.

Комбінаторне доведення

Після виходу роботи Коннеллі та інших Ілеана Штрейну опублікувала спрощене комбінаторне доведення, сформульоване в термінології планування рухів руки робота. Як оригінальне доведення, так і доведення за Штрейну знаходять безперервний рух, за якого ніякі дві точки не рухаються назустріч одна одній. У версії доведення Штрейну до початкової форми додаються ребра для утворення неопуклої псевдотріангуляції, видаляється одне з доданих ребер опуклої оболонки цього графа і показується, що граф, який залишився, має однопараметричне сімейство рухів, у яких відстані не зменшуються. Якщо повторно застосовувати ці рухи, зрештою, вони призведуть до стану, в якому ніякий розширювальний рух не можливий, що буває, коли ланцюжок витягується в лінійку або многокутник стає опуклим.

Штрейну і Вітлі навели застосування цього результату до математики оригамі — вони описали, як скласти будь-яке одновершинне оригамі, використовуючи тільки руху паперу без перетинів. По суті, цей процес складання є оберненою в часі версією задачі перетворення многокутника в опуклу форму, але на поверхні сфери, а не на евклідовій площині. Цей результат Паніна і Штрейну розширили на сферичні многокутники з довжиною ребра, меншою 2π.

Узагальнення

Джон Пардон узагальнив задачу про складний метр для спрямлюваних кривих. Він показав, що будь-яка спрямлювана жорданова крива може бути зроблена опуклою без збільшення довжини і без зменшення відстані між будь-якими двома точками кривої. За це дослідження, яке він виконав, ще будучи учнем середньої школи, Пардон отримав другу премію 2007 року в змаганні [en].

Див. також

  • Вкорочувальний потік, неперервне перетворення замкнутої кривої на площині, яке зрештою приводить до опуклої кривої.

Примітки

  1. Простота многокутника означає відсутність перетинів сторін.
  2. Connelly, Demaine, Rote, 2003.
  3. Streinu, Whiteley, 2005.
  4. Panina, Streinu, 2010.
  5. Pardon, 2009.
  6. Cunningham, 2007.

Література

  • Панина Г.Ю. О шарнирных механизмах, пружинных графах и вывернутых наизнанку многогранниках. — 2008. Стаття є замітками за лекцією в Літній школі «Сучасна математика» , 2008
  • Robert Connelly, Erik Demaine, Günter Rote. Straightening polygonal arcs and convexifying polygonal cycles // . — 2003. — Т. 30, вип. 2. — С. 205–239. — DOI:10.1007/s00454-003-0006-7.. Попередня версія на 41-ому щорічному симпозіумі , 2000.
  • Aimee Cunningham. The Next Generation // Science News. — 2007. — С. 166..
  • Ileana Streinu. . — IEEE Computer Society, 2000. — С. 443–453. — DOI:10.1109/SFCS.2000.892132.
  • Gaiane Panina, Ileana Streinu. Flattening single-vertex origami: The non-expansive case // Computational Geometry: Theory and Applications. — 2010. — Т. 43, вип. 8. — С. 678–687. — arXiv:1003.3490. — DOI:10.1016/j.comgeo.2010.04.002.
  • John Pardon. On the unfolding of simple closed curves // Transactions of the American Mathematical Society. — 2009. — Т. 361, вип. 4. — С. 1749–1764. — DOI:10.1090/S0002-9947-08-04781-8..
  • Ileana Streinu, Walter Whiteley. Discrete and Computational Geometry: Japanese Conference, JCDCG 2004, Tokyo, Japan, October 8-11, 2004, Revised Selected Papers. — Springer-Verlag, 2005. — Т. 3742. — С. 161–173. — (Lecture Notes in Computer Science).

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Zadacha pro skladanij metr ce zadacha kombinatornoyi geometriyi yaku mozhna sformulyuvati tak Chi mozhna lancyuzhok vidrizkiv sho ne peretinayutsya peretvoriti neperervnim ruhom bez peretinannya vidrizkiv tak sho vsi vershini lancyuzhka miscya z yednannya vidrizkiv budut lezhati na odnij pryamij Tisno pov yazana zadacha pokazati sho bud yakij prostij mnogokutnik mozhna peretvoriti do opuklogo viglyadu bezperervnim peretvorennyam iz zberezhennyam pid chas ruhu dovzhin storin pri comu pid chas ruhu mnogokutnik zalishayetsya prostim Obidvi zadachi buli uspishno rozv yazani grupoyu Konnelli Demejn Rout IstoriyaZadacha postavlena v 1970 roci en zalishalasya vidkritoyu protyagom 30 rokiv Popri pozirnu prostotu zadacha ne maye elementarnogo rozv yazku Shob zrozumiti tonkist pitannya zamist skladanogo metra rozglyanemo sharnirnij mehanizm sho realizuye graf derevo Ne kozhne take derevo mozhna rozpryamiti Tak u grafa pavuchka ne mozhna rozpryamiti nogi unikayuchi samoperetiniv i zalishayuchis u ploshini Cej pavuchok yakijs chas nadihav sprobi matematikiv pobuduvati nerozpryamlyuvanij skladanij metr voni namagalisya pobuduvati lamanu sho dvichi obhodit kontur pavuchka Kombinatorne dovedennyaPislya vihodu roboti Konnelli ta inshih Ileana Shtrejnu opublikuvala sproshene kombinatorne dovedennya sformulovane v terminologiyi planuvannya ruhiv ruki robota Yak originalne dovedennya tak i dovedennya za Shtrejnu znahodyat bezperervnij ruh za yakogo niyaki dvi tochki ne ruhayutsya nazustrich odna odnij U versiyi dovedennya Shtrejnu do pochatkovoyi formi dodayutsya rebra dlya utvorennya neopukloyi psevdotriangulyaciyi vidalyayetsya odne z dodanih reber opukloyi obolonki cogo grafa i pokazuyetsya sho graf yakij zalishivsya maye odnoparametrichne simejstvo ruhiv u yakih vidstani ne zmenshuyutsya Yaksho povtorno zastosovuvati ci ruhi zreshtoyu voni prizvedut do stanu v yakomu niyakij rozshiryuvalnij ruh ne mozhlivij sho buvaye koli lancyuzhok vityaguyetsya v linijku abo mnogokutnik staye opuklim Shtrejnu i Vitli naveli zastosuvannya cogo rezultatu do matematiki origami voni opisali yak sklasti bud yake odnovershinne origami vikoristovuyuchi tilki ruhu paperu bez peretiniv Po suti cej proces skladannya ye obernenoyu v chasi versiyeyu zadachi peretvorennya mnogokutnika v opuklu formu ale na poverhni sferi a ne na evklidovij ploshini Cej rezultat Panina i Shtrejnu rozshirili na sferichni mnogokutniki z dovzhinoyu rebra menshoyu 2p UzagalnennyaDzhon Pardon uzagalniv zadachu pro skladnij metr dlya spryamlyuvanih krivih Vin pokazav sho bud yaka spryamlyuvana zhordanova kriva mozhe buti zroblena opukloyu bez zbilshennya dovzhini i bez zmenshennya vidstani mizh bud yakimi dvoma tochkami krivoyi Za ce doslidzhennya yake vin vikonav she buduchi uchnem serednoyi shkoli Pardon otrimav drugu premiyu 2007 roku v zmaganni en Div takozhVkorochuvalnij potik neperervne peretvorennya zamknutoyi krivoyi na ploshini yake zreshtoyu privodit do opukloyi krivoyi PrimitkiProstota mnogokutnika oznachaye vidsutnist peretiniv storin Connelly Demaine Rote 2003 Streinu Whiteley 2005 Panina Streinu 2010 Pardon 2009 Cunningham 2007 LiteraturaPanina G Yu O sharnirnyh mehanizmah pruzhinnyh grafah i vyvernutyh naiznanku mnogogrannikah 2008 Stattya ye zamitkami za lekciyeyu v Litnij shkoli Suchasna matematika 2008 Robert Connelly Erik Demaine Gunter Rote Straightening polygonal arcs and convexifying polygonal cycles 2003 T 30 vip 2 S 205 239 DOI 10 1007 s00454 003 0006 7 Poperednya versiya na 41 omu shorichnomu simpoziumi 2000 Aimee Cunningham The Next Generation Science News 2007 S 166 Ileana Streinu IEEE Computer Society 2000 S 443 453 DOI 10 1109 SFCS 2000 892132 Gaiane Panina Ileana Streinu Flattening single vertex origami The non expansive case Computational Geometry Theory and Applications 2010 T 43 vip 8 S 678 687 arXiv 1003 3490 DOI 10 1016 j comgeo 2010 04 002 John Pardon On the unfolding of simple closed curves Transactions of the American Mathematical Society 2009 T 361 vip 4 S 1749 1764 DOI 10 1090 S0002 9947 08 04781 8 Ileana Streinu Walter Whiteley Discrete and Computational Geometry Japanese Conference JCDCG 2004 Tokyo Japan October 8 11 2004 Revised Selected Papers Springer Verlag 2005 T 3742 S 161 173 Lecture Notes in Computer Science

Дата публікації:
Топ