Кривая момента
В геометрии — кривая момента это алгебраическая кривая в d -мерном евклидовом пространстве, заданная набором точек с декартовыми координатами вида
В евклидовой плоскости моментная кривая представляет собой параболу , а в трехмерном пространстве — скрученную кубику . Ее замыканием в проективном пространстве является рациональная нормальная кривая .
Кривые моментов использовались для нескольких приложений в дискретной геометрии , включая циклические многогранники , задачу отсутствия трех рядов и геометрическое доказательство хроматического числа графов Кнезера .
Характеристики
[ редактировать ]Каждая гиперплоскость пересекает кривую момента в конечном множестве, состоящем не более чем из d точек. Если гиперплоскость пересекает кривую ровно в d точках, то кривая пересекает гиперплоскость в каждой точке пересечения. Таким образом, каждая конечная точка, заданная на кривой моментов, находится в аффинном общем положении . [2]
Приложения
[ редактировать ]Выпуклая оболочка любого конечного набора точек на кривой моментов представляет собой циклический многогранник . [3] Циклические многогранники имеют максимально возможное количество граней для заданного числа вершин, а в размерностях четыре и более обладают свойством, заключающимся в том, что их ребра образуют полный граф . В более строгом смысле они являются соседними многогранниками , что означает, что каждый набор из не более d /2 вершин многогранника образует одну из его граней. Наборы точек на кривой момента также реализуют максимально возможное количество симплексов, , среди всех возможных триангуляций Делоне наборов из n точек в d измерениях. [4]
В евклидовой плоскости можно разделить любую площадь или меру на четыре равных подмножества, используя теорему о сэндвиче с ветчиной . Аналогичным образом, но более сложно, любой объем или мера в трех измерениях может быть разделена на восемь равных подмножеств тремя плоскостями. Однако этот результат не распространяется на пять или более измерений, поскольку кривая момента дает примеры наборов, которые нельзя разделить на 2. д подмножества d гиперплоскостями. В частности, в пяти измерениях наборы из пяти гиперплоскостей могут разделить сегменты кривой момента не более чем на 26 частей. Неизвестно, всегда ли возможны четырехмерные разбиения на 16 равных подмножеств с помощью четырех гиперплоскостей, но можно разбить 16 точек четырехмерной кривой момента на 16 ортантов набора из четырех гиперплоскостей. [5]
Конструкция, основанная на кривой моментов, может быть использована для доказательства леммы Гейла, согласно которой для любых целых положительных чисел k и d можно разместить 2 k + d точек на d -мерной сфере так, что каждое открытое полушарие содержит не менее k точек. Эту лемму, в свою очередь, можно использовать для вычисления хроматического числа графов Кнезера — проблемы, впервые иным способом решенной Ласло Ловасом . [6]
Кривая моментов также использовалась при рисовании графов , чтобы показать, что все n -вершинные графы могут быть нарисованы с их вершинами в трехмерной целочисленной сетке с длиной стороны O( n ) и без двух пересекающихся ребер. Основная идея состоит в том, чтобы выбрать простое число p, большее n , и поместить вершину i графа в координаты
- ( я , я 2 мод р , я 3 против п ). [7]
Тогда плоскость может пересечь кривую только в трех положениях. Поскольку два пересекающихся ребра должны иметь четыре вершины в одной плоскости, этого никогда не произойдет.Аналогичная конструкция, использующая кривую момента по модулю простого числа, но в двух измерениях, а не в трех, обеспечивает линейную оценку для задачи отсутствия трех рядов . [8]
Примечания
[ редактировать ]- ^ Матушек (2002) , Определение 5.4.1, стр. 97; Матушек (2003) , Определение 1.6.3, стр. 17.
- ^ Эдельсбруннер (1987) , стр. 100; Матушек (2002) , Лемма 5.4.2, стр. 97; Матушек (2003) , Лемма 1.6.4, стр. 17.
- ^ Гейл (1963) ; Эдельсбруннер (1987) , стр. 101; Матушек (2002) , Лемма 5.4.2, стр. 97.
- ^ Амента, Аттали и Девиллерс (2007) .
- ^ Эдельсбруннер (1987) , стр. 70–79; Матушек (2003) , стр. 50–51.
- ^ Матушек (2003) , раздел 3.5, лемма Гейла и теорема Шрийвера, стр. 64–67. Использование леммы Гейла для задачи раскраски принадлежит Барани (1978) .
- ^ Коэн и др. (1997) .
- ↑ Приписано Ротом (1951) Полу Эрдешу .
Ссылки
[ редактировать ]- Амента, Нина ; Аттали, Доминик; Девиллерс, Оливье (2007), «Сложность триангуляции Делоне для точек на многогранниках меньшей размерности», Труды восемнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , Нью-Йорк: ACM, стр. 1106–1113, MR 2485262 .
- Барань И. (1978), «Краткое доказательство гипотезы Кнезера», Журнал комбинаторной теории , серия A, 25 (3): 325–326, doi : 10.1016/0097-3165(78)90023-7 , MR 0514626 .
- Коэн, РФ; Идс, П .; Лин, Тао; Раски, Ф. (1997), «Чертеж трехмерного графика», Algorithmica , 17 (2): 199–208, doi : 10.1007/BF02522826 , MR 1425733 .
- Эдельсбруннер, Герберт (1987), Алгоритмы в комбинаторной геометрии , Монографии EATCS по теоретической информатике, том. 10, Берлин: Springer-Verlag, ISBN 3-540-13722-Х , МР 0904271 .
- Гейл, Дэвид (1963), «Соседние и циклические многогранники», в Клее, Виктор (ред.), Выпуклость, Сиэтл, 1961 , Симпозиумы по чистой математике, том. 7, Провиденс, Род-Айленд: Американское математическое общество, стр. 225–232, MR 0152944 .
- Матушек, Иржи (2002), Лекции по дискретной геометрии , Тексты для аспирантов по математике , том. 212, Шпрингер-Верлаг, ISBN 978-0-387-95373-1 .
- Матушек, Иржи (2003), Использование теоремы Борсука-Улама: лекции по топологическим методам в комбинаторике и геометрии , Universitext, Springer, ISBN 978-3-540-00362-5 .
- Рот, К.Ф. (1951), «О проблеме Гейльбронна», Журнал Лондонского математического общества , 26 (3): 198–204, doi : 10.1112/jlms/s1-26.3.198 .