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

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

$(x,x^2,x^3,\dots ,x^d)$Шаблон:SfnШаблон:Sfn.

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

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

Властивості

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

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

Опукла оболонка будь-якої скінченної множини точок на кривій моментів є циклічним багатогранникомШаблон:SfnШаблон:SfnШаблон:Sfn. Циклічні багатогранники мають найбільше число граней за заданого числа вершин, а в розмірностях чотири і вище багатогранники мають властивість, що їх ребра утворюють повний граф. Більш строго, вони є суміжнісними багатогранниками, що означає, що будь-який набір не більше ніж d/2 вершин багатогранника утворює одну з його граней. Множини точок на кривій моментів також реалізують максимально можливе число симплексів, $\mathrm{\Omega }(n^{\lceil d/2\rceil })$, серед усіх можливих тріангуляцій Делоне множини з n точок у d-вимірному просторіШаблон:Sfn.

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

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

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

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

Література

• Шаблон:Книга.
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття