Curva de momentos

En geometría, una curva de momentos es una entidad algebraica dada en un espacio euclídeo de dimensión d a la que pertenenece un conjunto de puntos con coordenadas cartesianas de la forma

$\left(x,x^{2},x^{3},\dots ,x^{d}\right).$​

En el espacio bidimensional, la curva de momentos es una parábola, mientras que en el espacio tridimensional es un cúbica alabeada. Su cierre en el espacio proyectivo es una curva normal racional.

Las curvas de momentos se han utilizado para varias aplicaciones en geometría discreta, incluidos politopos cíclicos, el problema de sin tres en línea y una prueba geométrica de coloración de grafos del grafo de Kneser.

Propiedades

Cada hiperplano interseca la curva de momentos en un conjunto finito de como máximo d puntos. Si un hiperplano interseca la curva exactamente en los mencionados d puntos, entonces la curva cruza el hiperplano en cada punto de intersección. Por lo tanto, cada punto finito establecido en la curva de momentos está en posición general lineal.​

Aplicaciones

La envolvente convexa de cualquier conjunto finito de puntos en una curva de momentos es un politopo cíclico.​ Los politopos cíclicos tienen el mayor número posible de caras para un número dado de vértices, y en dimensiones cuatro o más tienen la propiedad de que sus aristas forman un grafo completo. Más fuertemente, son politopos vecinos, lo que significa que cada conjunto de como máximo d/2 vértices del politopo forma una de sus caras. Los conjuntos de puntos en la curva de momentos también realizan el máximo número posible de simples, $\Omega (n^{\lceil d/2\rceil })$, entre todas las triangulaciones de Delaunay posibles de conjuntos de n puntos en d dimensiones.​

En el espacio bidimensional, es posible dividir cualquier área o medida en cuatro subconjuntos iguales, utilizando el teorema del sándwich de jamón. De manera similar pero más complicada, cualquier volumen o medida en tres dimensiones puede dividirse en ocho subconjuntos iguales mediante tres planos. Sin embargo, este resultado no se generaliza a cinco o más dimensiones, ya que la curva de momentos proporciona ejemplos de conjuntos que no se pueden dividir en 2^d subconjuntos mediante d hiperplanos. En particular, en cinco dimensiones, conjuntos de cinco hiperplanos pueden dividir segmentos de la curva de momentos en un máximo de 26 partes. No se sabe si las particiones de cuatro dimensiones en 16 subconjuntos iguales por cuatro hiperplanos son siempre posibles, pero es posible dividir 16 puntos en la curva de momentos de cuatro dimensiones en los 16 ortantes de un conjunto de cuatro hiperplanos.​

Se puede utilizar una construcción basada en la curva de momentos para demostrar un lema de Gale, según el cual, para cualesquiera enteros positivos k y d, es posible colocar 2k + d puntos en una esfera de dimensión d de tal manera que cada hemisferio abierto contiene al menos k puntos. Este lema, a su vez, se puede usar para calcular la coloración de los grafos de Kneser, un problema que László Lovász resolvió primero de manera diferente.​

La curva de momentos también se ha utilizado en dibujo de grafos, para mostrar que todos los grafos de n vértices se pueden dibujar con sus vértices en una cuadrícula entera tridimensional de longitud lateral O(n) y sin dos cruces entre sus vínculos. La idea principal es elegir un número primo p mayor que n y colocar el vértice i del grafo en las coordenadas

(i, i ² mod p, i ³ mod p).​

Entonces un plano solo puede cruzar la curva en tres posiciones. Dado que dos vínculos que se cruzan deben tener cuatro vértices en el mismo plano, esto nunca puede suceder.

Una construcción similar que usa la curva de momentos módulo un número primo, pero en dos dimensiones en lugar de tres, proporciona un límite lineal para el problema de sin tres en línea.​

Bibliografía

• Amenta, Nina; Attali, Dominique; Devillers, Olivier (2007), «Complexity of Delaunay triangulation for points on lower-dimensional polyhedra», Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New York: ACM, pp. 1106-1113, MR 2485262 ..
• Bárány, I. (1978), «A short proof of Kneser's conjecture», Journal of Combinatorial Theory, Series A 25 (3): 325-326, MR 514626, doi:10.1016/0097-3165(78)90023-7 ..
• Cohen, R. F.; Eades, P.; Lin, Tao; Ruskey, F. (1997), «Three-dimensional graph drawing», Algorithmica 17 (2): 199-208, MR 1425733, doi:10.1007/BF02522826 ..
• Edelsbrunner, Herbert (1987), Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical Computer Science 10, Berlin: Springer-Verlag, ISBN 3-540-13722-X, MR 904271 ..
• Gale, David (1963), «Neighborly and cyclic polytopes», en Klee, Victor, ed., Convexity, Seattle, 1961, Symposia in Pure Mathematics 7, Providence, R.I.: American Mathematical Society, pp. 225-232, MR 0152944 ..
• Matoušek, Jiří (2002), Lectures on Discrete Geometry, Graduate Texts in Mathematics 212, Springer-Verlag, ISBN 978-0-387-95373-1 ..
• Matoušek, Jiří (2003), Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry, Universitext, Springer, ISBN 978-3-540-00362-5 ..
• Roth, K. F. (1951), «On a problem of Heilbronn», London Mathematical Society 26 (3): 198-204, doi:10.1112/jlms/s1-26.3.198 ..

• Datos: Q6897111