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

Перейти к навигацииПерейти к поиску

Кривая моментов — алгебраическая кривая в 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. ↑ 1 2 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.