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

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

[1][2].

На евклидовой плоскости кривая моментов — это парабола, а в трёхмерном пространстве — скрученная кубическая кривая. Её замыкание в проективном пространстве — рациональная нормальная кривая.

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

Свойства

Любая гиперплоскость имеет с кривой не более чем 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]

Примечания
  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 // 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.