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

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

$\left(x,x^{2},x^{3},\dots ,x^{d}\right)$.

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

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

Властивості

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

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

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

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

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

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

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

Література

• 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 // Journal of Combinatorial Theory. — 1978. — Т. 25, вип. 3 (11 листопада). — (Series A). — DOI:10.1016/0097-3165(78)90023-7.
• Cohen R. F., Eades P., Lin Tao, Ruskey F. Three-dimensional graph drawing // Algorithmica. — 1997. — Т. 17, вип. 2 (11 листопада). — С. 199–208. — DOI:10.1007/BF02522826.
• Herbert Edelsbrunner. Algorithms in Combinatorial Geometry. — Berlin : Springer-Verlag, 1987. — Т. 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. — Т. 7. — С. 225–232. — (Symposia in Pure Mathematics)
• Jiří Matoušek. Lectures on Discrete Geometry. — Springer-Verlag, 2002. — Т. 212. — (Graduate Texts in Mathematics) — ISBN 978-0-387-95373-1.
• Jiří Matoušek. 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. — Т. 26, вип. 3 (11 листопада). — С. 198–204. — DOI:10.1112/jlms/s1-26.3.198.