Крива моментівКрива́ моме́нтів — це алгебрична крива в d-вимірному евклідовому просторі, задана множиною точок з декартовими координатами На евклідовій площині крива моментів — це парабола, а в тривимірному просторі — скручена кубика[en]. Її замикання у проєктивному просторі — раціональна нормальна крива. Криві моментів використовують у деяких застосуваннях комбінаторної геометрії, таких як циклічні багатогранники, задача «жодні три точки на одній прямій»[en] і геометричне доведення хроматичного числа графів Кнезера. ВластивостіБудь-яка гіперплощина має з кривою не більше ніж d спільних точок. Якщо гіперплощина має рівно d спільних точок з кривою, то крива перетинає гіперплощину в кожній такій точці (тобто не дотикається). Таким чином, будь-яка скінченна множина точок на кривій моментів перебуває в загальному лінійному положенні[3][4][5]. ЗастосуванняОпукла оболонка будь-якої скінченної множини точок на кривій моментів є циклічним багатогранником[6][7][4]. Циклічні багатогранники мають найбільше число граней за заданого числа вершин, а в розмірностях чотири і вище багатогранники мають властивість, що їх ребра утворюють повний граф. Більш строго, вони є суміжнісними багатогранниками, що означає, що будь-який набір не більше ніж d/2 вершин багатогранника утворює одну з його граней. Множини точок на кривій моментів також реалізують максимально можливе число симплексів, , серед усіх можливих тріангуляцій Делоне множини з n точок у d-вимірному просторі[8]. На евклідовій площині можна розділити будь-яку вимірну ділянку на чотири рівних (за мірою) підмножини (за теоремою про бутерброд). Аналогічно, але складніше, будь-яку вимірну множину в тривимірному просторі можна розбити на вісім рівних (за мірою) підмножин трьома площинами. Однак цей результат не узагальнюється на п'ять або вище розмірностей, оскільки крива моментів дає приклад множин, які не можна розбити на 2d підмножин d гіперплощинами. Зокрема, в п'ятивимірному просторі множина з п'яти гіперплощин може розбити криву моментів на не більше ніж 26 сегментів. Невідомо, чи завжди можна розбити в чотиривимірному просторі криву моментів на 16 рівних частин п'ятьма гіперплощинами, але можна розбити 16 точок на чотиривимірній кривий моментів на 16 ортантів набору з чотирьох гіперплощин[9][10]. Побудову, засновану на кривій моментів, можна також використати для доведення леми Гейла, згідно з якою для будь-яких додатних k і d можна розмістити 2k + d точок на d-вимірній сфері так, що будь-яка відкрита півсфера міститиме не менше ніж k точок. Цю лему в свою чергу можна використовувати для обчислення хроматичного числа кнезерових графів, задачі, яку розв'язав Ласло Ловас іншим способом[11][12]. Крива моментів використовується також для візуалізації графів, щоб показати, що всі графи з n вершинами можна намалювати з вершинами на тривимірній цілочисельній ґратці з довжиною сторони O(n) без перетину ребер. Головна ідея — вибрати просте число p, більше від n, і поміщати вершини i графу в точку з координатами: (i, i 2 mod p, i 3 mod p)[13]. Тоді площина може перетнути криву тільки в трьох точках. Оскільки два ребра, що перетинаються, повинні мати чотири вершини на тій самій площині, цього не може статися. Подібна побудова використовує криву моментів за модулем простого числа, але в двовимірному просторі, а не в тривимірному, що дає лінійну границю числа точок для задачі «жодні три точки на одній прямій»[14]. Примітки
Література
|
Portal di Ensiklopedia Dunia