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

Кривая моментов — алгебраическая кривая в d-мерном евклидовом пространстве, заданная множеством точек с декартовыми координатами^[1][2]

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

На евклидовой плоскости кривая моментов — это парабола. Замыкание кривой моментов в проективном пространстве — рациональная нормальная кривая.

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

Любая гиперплоскость имеет с кривой не более чем d общих точек. Если гиперплоскость имеет в точности d общих точек с кривой, то кривая проходит через гиперплоскость в каждой такой точке (то есть не касается). Таким образом, любое конечное множество точек на кривой моментов находится в общем линейном положении^[3][4][5].

Выпуклая оболочка любого конечного множества точек на кривой моментов является циклическим многогранником^[6][7][4]. Циклические многогранники имеют наибольшее число граней при заданном числе вершин, а в размерностях четыре и выше многогранники имеют свойство, что их рёбра образуют полный граф. Более строго, они являются смежностыми многогранниками, что означает, что любой набор не более чем d/2 вершин многогранника образует одну из его граней. Множества точек на кривой моментов также реализует максимально возможное число симплексов, ${\displaystyle \Omega (n^{\lceil d/2\rceil })}$, среди всех возможных триангуляций Делоне множеств из n точек в d-мерном пространстве^[8].

На евклидовой плоскости можно разделить любую измеримую область на четыре равных (по мере) подмножества (по теореме о сэндвиче^[англ.]). Аналогично, но более сложно, любое измеримое множество в трёхмерном пространстве может быть разбито на восемь равных (по мере) подмножеств тремя плоскостями. Однако этот результат не обобщается на пять или выше размерностей, поскольку кривая моментов даёт пример множеств, которые нельзя разбить на 2^d подмножеств d гиперплоскостями. В частности, в пятимерном пространстве множество из пяти гиперплоскостей может разбить кривую моментов на не более чем 26 сегментов. Неизвестно, всегда ли можно разбить в четырёхмерном пространстве кривую моментов на 16 равных частей пятью гиперплоскостями, но можно разбить 16 точек на четырёхмерной кривой моментов на 16 ортантов набора из четырёх гиперплоскостей^[9][10].

Построение, основанное на кривой моментов, может быть также использовано для доказательства леммы Гейла, согласно которой для любых положительных k и d можно разместить 2k + d точек на d-мерной сфере таким образом, что любая открытая полусфера содержит не менее k точек. Эту лемму, в свою очередь, можно использовать для вычисления хроматического числа кнезеровских графов, задачи, которую решил Ласло Ловас другим способом^[11][12].

Кривая моментов используется также для визуализации графов, чтобы показать, что все графы с n вершинами можно нарисовать с вершинами на трёхмерной целочисленной решётке с длиной стороны O(n) без пересечения рёбер. Главная идея — выбрать простое число p, большее n, и помещать вершины i графа в точку с координатами

(i, i ² mod p, i ³ mod p)^[13].

Тогда плоскость может пересечь кривую только в трёх точках. Поскольку два пересекающихся ребра должны иметь четыре вершины на той же плоскости, это не может произойти. Подобное построение использует кривую моментов по модулю простого числа, но в двухмерном пространстве, а не в трёхмерном, что даёт линейную границу числа точек для задачи «никакие три точки на одной прямой»^[англ.].^[14]

• 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. — 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. — С. 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. — С. 198–204. — doi:10.1112/jlms/s1-26.3.198.

У этой статьи есть несколько проблем, помогите их исправить: Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (27 октября 2017) Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (27 октября 2017) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.