Curva de momento

La curva de momento es una curva algebraica en el espacio euclidiano d - dimensional dada por un conjunto de puntos con coordenadas cartesianas

[1] [2] .

En el plano euclidiano , la curva de momento es una parábola , y en el espacio tridimensional es una curva cúbica torcida . Su cierre en el espacio proyectivo es una curva normal racional .

Las curvas de momento se utilizan en algunas aplicaciones de la geometría combinatoria , como los poliedros cíclicos , el problema "no hay tres puntos en la misma línea" y la prueba geométrica del número cromático de los gráficos de Kneser .

Propiedades

Cualquier hiperplano tiene como máximo d puntos en común con una curva. Si el hiperplano tiene exactamente d puntos en común con la curva, entonces la curva interseca al hiperplano en cada uno de esos puntos (es decir, no se toca). Por lo tanto, cualquier conjunto finito de puntos en la curva de momento está en una posición lineal general [3] [4] [5] .

Aplicaciones

El casco convexo de cualquier conjunto finito de puntos en la curva de momento es un poliedro cíclico [6] [7] [4] . Los poliedros cíclicos tienen el mayor número de caras para un número dado de vértices, y en dimensiones cuatro y superiores, los poliedros tienen la propiedad de que sus aristas forman un gráfico completo . Más estrictamente, son politopos de adyacencia , lo que significa que cualquier conjunto de como máximo d /2 vértices de un politopo forma una de sus caras. El conjunto de puntos en la curva de momento también incorpora el máximo número posible de simples, entre todas las posibles triangulaciones de Delaunay de conjuntos de n puntos en un espacio d -dimensional [8] .

En el plano euclidiano , cualquier dominio medible se puede dividir en cuatro subconjuntos iguales (en medida) (por el teorema del sándwich ). De manera similar, pero más compleja, cualquier conjunto medible en un espacio tridimensional puede dividirse en ocho subconjuntos iguales (en medida) por tres planos. Sin embargo, este resultado no se generaliza a cinco o más dimensiones, ya que la curva de momentos da un ejemplo de conjuntos que no se pueden descomponer en 2 d subconjuntos mediante d hiperplanos. En particular, en un espacio de cinco dimensiones, un conjunto de cinco hiperplanos puede dividir la curva de momento en un máximo de 26 segmentos. No se sabe si siempre es posible dividir la curva de momento 4D en 16 partes iguales por cinco hiperplanos, pero es posible dividir 16 puntos en la curva de momento 4D en 16 ortantes de un conjunto de cuatro hiperplanos [9] [10 ] .

La construcción basada en la curva de momento también se puede utilizar para probar el lema de Gale, según el cual, para cualquier k y d positivos, se pueden colocar 2 k  +  d puntos en una esfera de dimensión d tal que cualquier hemisferio abierto contiene al menos k puntos. Este lema, a su vez, se puede utilizar para calcular el número cromático de los gráficos de Kneser , problema que Laszlo Lovas resolvió de otra forma [11] [12] .

La curva de momento también se usa para la visualización de gráficos para mostrar que todos los gráficos con n vértices se pueden dibujar con vértices en una red de enteros tridimensional con longitud de lado O( n ) sin bordes cruzados. La idea principal es elegir un número primo p mayor que n y colocar los vértices i del gráfico en el punto con coordenadas

( yo , yo 2  mod  p , i 3  mod  p ) [13] .

Entonces el plano puede intersecar la curva solo en tres puntos. Como dos aristas que se cortan deben tener cuatro vértices en el mismo plano, esto no puede suceder. Una construcción similar usa la curva de momentos módulo un número primo, pero en un espacio bidimensional, y no tridimensional, lo que da un límite lineal en el número de puntos para el problema "no hay tres puntos en una línea recta" . [catorce]

Notas

  1. ↑ Matousek, 2002 , pág. 97, Definición 5.4.1.
  2. ↑ Matousek, 2003 , pág. 17, Definición 1.6.3.
  3. ↑ Edelsbrunner, 1987 , pág. 100.
  4. ↑ 1 2 Matousek, 2002 , pág. 97, Lema 5.4.2.
  5. ↑ Matousek, 2003 , pág. 17, Lema 1.6.4.
  6. ↑ Vendaval, 1963 .
  7. ↑ Edelsbrunner, 1987 , pág. 101.
  8. ↑ Amenta, Attali, Devillers, 2007 .
  9. ↑ Edelsbrunner, 1987 , pág. 70–79.
  10. ↑ Matousek, 2003 , pág. 50–51.
  11. ↑ Matousek, 2003 , pág. 64–67, Sección 3.5, Lema de Gale y Teorema de Schreiver.
  12. ↑ Barany, 1978 , p. 325–326, El uso del lema de Gale para el problema de coloración.
  13. ↑ Cohen, Eades, Lin, Ruskey, 1997 .
  14. ↑ Roth ( 1951 ) atribuye la tarea a Erdős .

Literatura