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

Крива моме нтів це алгебрична крива в d вимірному евклідовому просторі задана множиною точок з декартовими координатами

Крива моментів

Крива моментів

Крива́ моме́нтів — це алгебрична крива в d-вимірному евклідовому просторі, задана множиною точок з декартовими координатами

.

На евклідовій площині крива моментів — це парабола, а в тривимірному просторі — [en]. Її замикання у проєктивному просторі — раціональна нормальна крива.

Криві моментів використовують у деяких застосуваннях комбінаторної геометрії, таких як циклічні багатогранники, [en] і геометричне доведення хроматичного числа графів Кнезера.

Властивості

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

Застосування

Опукла оболонка будь-якої скінченної множини точок на кривій моментів є циклічним багатогранником. Циклічні багатогранники мають найбільше число граней за заданого числа вершин, а в розмірностях чотири і вище багатогранники мають властивість, що їх ребра утворюють повний граф. Більш строго, вони є суміжнісними багатогранниками, що означає, що будь-який набір не більше ніж d/2 вершин багатогранника утворює одну з його граней. Множини точок на кривій моментів також реалізують максимально можливе число симплексів, image, серед усіх можливих тріангуляцій Делоне множини з n точок у d-вимірному просторі.

На евклідовій площині можна розділити будь-яку вимірну ділянку на чотири рівних (за мірою) підмножини (за теоремою про бутерброд). Аналогічно, але складніше, будь-яку вимірну множину в тривимірному просторі можна розбити на вісім рівних (за мірою) підмножин трьома площинами. Однак цей результат не узагальнюється на п'ять або вище розмірностей, оскільки крива моментів дає приклад множин, які не можна розбити на 2d підмножин d гіперплощинами. Зокрема, в п'ятивимірному просторі множина з п'яти гіперплощин може розбити криву моментів на не більше ніж 26 сегментів. Невідомо, чи завжди можна розбити в чотиривимірному просторі криву моментів на 16 рівних частин п'ятьма гіперплощинами, але можна розбити 16 точок на чотиривимірній кривий моментів на 16 ортантів набору з чотирьох гіперплощин.

Побудову, засновану на кривій моментів, можна також використати для доведення леми Гейла, згідно з якою для будь-яких додатних k і d можна розмістити 2k + d точок на d-вимірній сфері так, що будь-яка відкрита півсфера міститиме не менше ніж k точок. Цю лему в свою чергу можна використовувати для обчислення хроматичного числа кнезерових графів, задачі, яку розв'язав Ласло Ловас іншим способом.

Крива моментів використовується також для візуалізації графів, щоб показати, що всі графи з n вершинами можна намалювати з вершинами на тривимірній цілочисельній ґратці з довжиною сторони O(n) без перетину ребер. Головна ідея — вибрати просте число p, більше від n, і поміщати вершини i графу в точку з координатами: (i, i 2 mod p, i 3 mod p).

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

Примітки

  1. Matoušek, 2002, с. 97, Definition 5.4.1.
  2. Matoušek, 2003, с. 17, Definition 1.6.3.
  3. Edelsbrunner, 1987, с. 100.
  4. Matoušek, 2002, с. 97, Lemma 5.4.2.
  5. Matoušek, 2003, с. 17, Lemma 1.6.4.
  6. Gale, 1963.
  7. Edelsbrunner, 1987, с. 101.
  8. Amenta, Attali, Devillers, 2007.
  9. Edelsbrunner, 1987, с. 70–79.
  10. Matoušek, 2003, с. 50–51.
  11. Matoušek, 2003, с. 64–67, Секция 3.5, Лемма Гейла и теорема Схрейвера.
  12. Bárány, 1978, с. 325–326, The use of Gale's lemma for the coloring problem.
  13. Cohen, Eades, Lin, Ruskey, 1997.
  14. Рот (Roth, 1951) приписує задачу Ердешу.

Література

  • Nina Amenta, Dominique Attali, Olivier Devillers. Complexity of Delaunay triangulation for points on lower-dimensional polyhedra // Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. — New York : ACM, 2007. — С. 1106–1113..
  • Bárány I. A short proof of Kneser's conjecture // . — 1978. — Т. 25, вип. 3 (17 червня). — (Series A). — DOI:10.1016/0097-3165(78)90023-7.
  • Cohen R. F., Eades P., Lin Tao, Ruskey F. Three-dimensional graph drawing // . — 1997. — Т. 17, вип. 2 (17 червня). — С. 199–208. — DOI:10.1007/BF02522826.
  • Herbert Edelsbrunner. Algorithms in Combinatorial Geometry. — Berlin : Springer-Verlag, 1987. — Т. 10. — (EATCS Monographs on Theoretical Computer Science) — .
  • David Gale. Neighborly and cyclic polytopes // Convexity, Seattle, 1961 / Victor Klee. — Providence, R.I. : American Mathematical Society, 1963. — Т. 7. — С. 225–232. — (Symposia in Pure Mathematics)
  • Jiří Matoušek. Lectures on Discrete Geometry. — Springer-Verlag, 2002. — Т. 212. — () — .
  • Jiří Matoušek. Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry. — Springer, 2003. — (Universitext) — .
  • Roth K. F. On a problem of Heilbronn // Journal of the London Mathematical Society. — 1951. — Т. 26, вип. 3 (17 червня). — С. 198–204. — DOI:10.1112/jlms/s1-26.3.198.

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

Kriva mome ntiv ce algebrichna kriva v d vimirnomu evklidovomu prostori zadana mnozhinoyu tochok z dekartovimi koordinatami x x2 x3 xd displaystyle left x x 2 x 3 dots x d right Na evklidovij ploshini kriva momentiv ce parabola a v trivimirnomu prostori en Yiyi zamikannya u proyektivnomu prostori racionalna normalna kriva Krivi momentiv vikoristovuyut u deyakih zastosuvannyah kombinatornoyi geometriyi takih yak ciklichni bagatogranniki en i geometrichne dovedennya hromatichnogo chisla grafiv Knezera VlastivostiBud yaka giperploshina maye z krivoyu ne bilshe nizh d spilnih tochok Yaksho giperploshina maye rivno d spilnih tochok z krivoyu to kriva peretinaye giperploshinu v kozhnij takij tochci tobto ne dotikayetsya Takim chinom bud yaka skinchenna mnozhina tochok na krivij momentiv perebuvaye v zagalnomu linijnomu polozhenni ZastosuvannyaOpukla obolonka bud yakoyi skinchennoyi mnozhini tochok na krivij momentiv ye ciklichnim bagatogrannikom Ciklichni bagatogranniki mayut najbilshe chislo granej za zadanogo chisla vershin a v rozmirnostyah chotiri i vishe bagatogranniki mayut vlastivist sho yih rebra utvoryuyut povnij graf Bilsh strogo voni ye sumizhnisnimi bagatogrannikami sho oznachaye sho bud yakij nabir ne bilshe nizh d 2 vershin bagatogrannika utvoryuye odnu z jogo granej Mnozhini tochok na krivij momentiv takozh realizuyut maksimalno mozhlive chislo simpleksiv W n d 2 displaystyle Omega n lceil d 2 rceil sered usih mozhlivih triangulyacij Delone mnozhini z n tochok u d vimirnomu prostori Na evklidovij ploshini mozhna rozdiliti bud yaku vimirnu dilyanku na chotiri rivnih za miroyu pidmnozhini za teoremoyu pro buterbrod Analogichno ale skladnishe bud yaku vimirnu mnozhinu v trivimirnomu prostori mozhna rozbiti na visim rivnih za miroyu pidmnozhin troma ploshinami Odnak cej rezultat ne uzagalnyuyetsya na p yat abo vishe rozmirnostej oskilki kriva momentiv daye priklad mnozhin yaki ne mozhna rozbiti na 2d pidmnozhin d giperploshinami Zokrema v p yativimirnomu prostori mnozhina z p yati giperploshin mozhe rozbiti krivu momentiv na ne bilshe nizh 26 segmentiv Nevidomo chi zavzhdi mozhna rozbiti v chotirivimirnomu prostori krivu momentiv na 16 rivnih chastin p yatma giperploshinami ale mozhna rozbiti 16 tochok na chotirivimirnij krivij momentiv na 16 ortantiv naboru z chotiroh giperploshin Pobudovu zasnovanu na krivij momentiv mozhna takozh vikoristati dlya dovedennya lemi Gejla zgidno z yakoyu dlya bud yakih dodatnih k i d mozhna rozmistiti 2k d tochok na d vimirnij sferi tak sho bud yaka vidkrita pivsfera mistitime ne menshe nizh k tochok Cyu lemu v svoyu chergu mozhna vikoristovuvati dlya obchislennya hromatichnogo chisla knezerovih grafiv zadachi yaku rozv yazav Laslo Lovas inshim sposobom Kriva momentiv vikoristovuyetsya takozh dlya vizualizaciyi grafiv shob pokazati sho vsi grafi z n vershinami mozhna namalyuvati z vershinami na trivimirnij cilochiselnij gratci z dovzhinoyu storoni O n bez peretinu reber Golovna ideya vibrati proste chislo p bilshe vid n i pomishati vershini i grafu v tochku z koordinatami i i2 mod p i3 mod p Todi ploshina mozhe peretnuti krivu tilki v troh tochkah Oskilki dva rebra sho peretinayutsya povinni mati chotiri vershini na tij samij ploshini cogo ne mozhe statisya Podibna pobudova vikoristovuye krivu momentiv za modulem prostogo chisla ale v dvovimirnomu prostori a ne v trivimirnomu sho daye linijnu granicyu chisla tochok dlya PrimitkiMatousek 2002 s 97 Definition 5 4 1 Matousek 2003 s 17 Definition 1 6 3 Edelsbrunner 1987 s 100 Matousek 2002 s 97 Lemma 5 4 2 Matousek 2003 s 17 Lemma 1 6 4 Gale 1963 Edelsbrunner 1987 s 101 Amenta Attali Devillers 2007 Edelsbrunner 1987 s 70 79 Matousek 2003 s 50 51 Matousek 2003 s 64 67 Sekciya 3 5 Lemma Gejla i teorema Shrejvera Barany 1978 s 325 326 The use of Gale s lemma for the coloring problem Cohen Eades Lin Ruskey 1997 Rot Roth 1951 pripisuye zadachu Erdeshu LiteraturaNina Amenta Dominique Attali Olivier Devillers Complexity of Delaunay triangulation for points on lower dimensional polyhedra Proceedings of the Eighteenth Annual ACM SIAM Symposium on Discrete Algorithms New York ACM 2007 S 1106 1113 Barany I A short proof of Kneser s conjecture 1978 T 25 vip 3 17 chervnya Series A DOI 10 1016 0097 3165 78 90023 7 Cohen R F Eades P Lin Tao Ruskey F Three dimensional graph drawing 1997 T 17 vip 2 17 chervnya S 199 208 DOI 10 1007 BF02522826 Herbert Edelsbrunner Algorithms in Combinatorial Geometry Berlin Springer Verlag 1987 T 10 EATCS Monographs on Theoretical Computer Science ISBN 3 540 13722 X David Gale Neighborly and cyclic polytopes Convexity Seattle 1961 Victor Klee Providence R I American Mathematical Society 1963 T 7 S 225 232 Symposia in Pure Mathematics Jiri Matousek Lectures on Discrete Geometry Springer Verlag 2002 T 212 ISBN 978 0 387 95373 1 Jiri Matousek Using the Borsuk Ulam Theorem Lectures on Topological Methods in Combinatorics and Geometry Springer 2003 Universitext ISBN 978 3 540 00362 5 Roth K F On a problem of Heilbronn Journal of the London Mathematical Society 1951 T 26 vip 3 17 chervnya S 198 204 DOI 10 1112 jlms s1 26 3 198

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