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

Moment curve

В геометрия, то кривая момента является алгебраическая кривая в d-размерный Евклидово пространство заданный набором точек с Декартовы координаты формы

[1]

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

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

Характеристики

Каждый гиперплоскость пересекает моментную кривую в конечном множестве не более чем d точки. Если гиперплоскость пересекает кривую точно d точек, то кривая пересекает гиперплоскость в каждой точке пересечения. Таким образом, каждая конечная точка на кривой момента находится в общее линейное положение.[2]

Приложения

В выпуклый корпус любого конечного множества точек на моментной кривой является циклический многогранник.[3] Циклические многогранники имеют максимально возможное количество граней для заданного числа вершин, а в размерах четыре или более обладают тем свойством, что их ребра образуют полный график. Более того, они соседние многогранники, что означает, что каждый набор не более d/ 2 вершин многогранника образует одну из его граней. Наборы точек на моментной кривой также реализуют максимально возможное количество симплексов, среди всех возможных Триангуляции Делоне наборов п указывает в d размеры.[4]

в Евклидова плоскость, можно разделить любую площадь или меру на четыре равных подмножества, используя теорема о сэндвиче с ветчиной. Точно так же, но более сложно, любой объем или мера в трех измерениях можно разделить на восемь равных подмножеств с помощью трех плоскостей. Однако этот результат нельзя обобщить на пять или более измерений, поскольку кривая момента дает примеры множеств, которые нельзя разделить на 2d подмножества по d гиперплоскости. В частности, в пяти измерениях наборы из пяти гиперплоскостей могут разделить сегменты кривой момента максимум на 26 частей. Неизвестно, всегда ли возможно четырехмерное разбиение на 16 равных подмножеств четырьмя гиперплоскостями, но можно разбить 16 точек на четырехмерной моментной кривой на 16 ортантов набора из четырех гиперплоскостей.[5]

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

Кривая момента также использовалась в рисунок графика, чтобы показать, что все п-вершинные графы могут быть построены со своими вершинами в трехмерной целочисленной сетке с длиной стороны O (п) и без пересечения двух ребер. Основная идея - выбрать простое число п больше, чем п и разместить вершину я графика в координатах

(я, я 2 модп, я 3 модп).[7]

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

Примечания

  1. ^ Матушек (2002), Определение 5.4.1, с. 97; Матушек (2003), Определение 1.6.3, с. 17.
  2. ^ Эдельсбруннер (1987), п. 100; Матушек (2002), Лемма 5.4.2, с. 97; Матушек (2003), Лемма 1.6.4, с. 17.
  3. ^ Гейл (1963); Эдельсбруннер (1987), п. 101; Матушек (2002), Лемма 5.4.2, с. 97.
  4. ^ Амента, Аттали и Девиллерс (2007).
  5. ^ Эдельсбруннер (1987), стр. 70–79; Матушек (2003)С. 50–51.
  6. ^ Матушек (2003), Раздел 3.5, Лемма Гейла и теорема Шрайвера, стр. 64–67. Использование леммы Гейла для задачи раскраски связано с тем, что Барань (1978).
  7. ^ Cohen et al. (1997).
  8. ^ Автор: Рот (1951) к Пол Эрдёш.

Рекомендации