En la geometría discreta y la teoría de la discrepancia , el problema del triángulo de Heilbronn es un problema de colocar puntos dentro de una región en el plano, para evitar triángulos de área pequeña . Lleva el nombre de Hans Heilbronn , quien conjeturó antes de 1950 que el área más pequeña del triángulo es necesariamente, como mucho, inversamente proporcional al cuadrado del número de puntos. Se demostró que la conjetura de Heilbronn era falsa, pero se desconoce la tasa de crecimiento asintótica del área mínima del triángulo.
Definición
El problema puede definirse en términos de cualquier conjunto compacto D en el plano con un área distinta de cero, como el cuadrado unitario o el disco unitario . Si S es un conjunto de n puntos de D , entonces cada tres puntos de S determina un triángulo (posiblemente uno degenerado, con área cero). Sea Δ ( S ) el mínimo de las áreas de estos triángulos, y sea Δ ( n ) (para un número entero n ≥ 3) el superior de los valores de Δ ( S ).
La pregunta planteada por Heilbronn era dar una expresión, o coincidir con los límites superior e inferior asintóticos , para Δ ( n ). Es decir, el objetivo es encontrar una función f , descrita por una expresión de forma cerrada , y constantes c 1 y c 2 , tales que para todo n ,
- .
En términos de notación O grande , la desigualdad izquierda se puede escribir como Δ ( n ) = Ω ( f ( n )), la desigualdad derecha se puede escribir como Δ ( n ) = O ( f ( n )), y ambos de juntos pueden escribirse como Δ ( n ) = Θ ( f ( n )). La forma y el área de D pueden afectar los valores exactos de Δ ( n ), pero solo por un factor constante, por lo que no son importantes para su tasa de crecimiento asintótica.
Conjetura de Heilbronn y construcciones de límite inferior
Heilbronn conjeturó que
Como mostró Paul Erdős , no es posible un límite más pequeño: cuando n es un número primo , el conjunto de n puntos ( i , i 2 mod n ) en una cuadrícula de números enteros n × n no tiene tres puntos colineales y, por lo tanto, según la fórmula de Pick, cada de los triángulos que forman tiene un área de al menos 1/2. Cuando este conjunto de puntos de la cuadrícula se escala a un cuadrado unitario, forman un conjunto de puntos cuya área de triángulo más pequeña es al menos proporcional a 1 / n 2 , coincidiendo con el límite superior conjeturado de Heilbronn. [1] Si n no es primo, entonces una construcción similar usando el siguiente número primo mayor que n logra el mismo límite inferior asintótico.
Komlós, Pintz & Szemerédi (1982) finalmente refutaron la conjetura de Heilbronn, al encontrar conjuntos de puntos cuya área triangular más pequeña crece asintóticamente a medida que
Límites superiores
Trivialmente, ya sea triangulando el casco convexo del conjunto de puntos dado S o eligiendo triples consecutivos de puntos en el orden ordenado de sus coordenadas x , es posible mostrar que cada conjunto de puntos contiene un triángulo pequeño, cuya área es como máximo inversamente proporcional an . Roth (1951) fue el primero en probar un límite superior no trivial en Δ ( n ), de la forma [1]
El mejor límite conocido hasta la fecha es el de la forma
para alguna c constante , probado por Komlós, Pintz & Szemerédi (1981) . [3]
Formas y números específicos
Goldberg (1972) ha investigado las disposiciones óptimas de n puntos en un cuadrado, para n hasta 16. [4] Las construcciones de Goldberg para hasta seis puntos se encuentran en el límite del cuadrado, y se colocan para formar una transformación afín de la vértices de un polígono regular . Para valores mayores de n , Comellas y Yebra (2002) mejoraron los límites de Goldberg, y para estos valores las soluciones incluyen puntos dentro del cuadrado. [5] Estas construcciones han demostrado ser óptimas hasta en siete puntos. [6]
Variaciones
Ha habido muchas variaciones de este problema, incluido el caso de un conjunto de puntos uniformemente aleatorio, para el cual los argumentos basados en la complejidad de Kolmogorov o la aproximación de Poisson muestran que el valor esperado del área mínima es inversamente proporcional al cubo del número de puntos. . [7] [8] También se han estudiado las variaciones que involucran el volumen de simplices de dimensiones superiores . [9]
Ver también
- Conjunto Danzer , un conjunto de puntos que evita triángulos vacíos de gran superficie
Referencias
- ↑ a b Roth, KF (1951), "Sobre un problema de Heilbronn", Revista de la Sociedad Matemática de Londres , 26 (3): 198-204, doi : 10.1112 / jlms / s1-26.3.198.
- ^ Komlós, J .; Pintz, J .; Szemerédi, E. (1982), "Un límite inferior para el problema de Heilbronn", Journal of the London Mathematical Society , 25 (1): 13-24, doi : 10.1112 / jlms / s2-25.1.13 , MR 0645860.
- ^ Komlós, J .; Pintz, J .; Szemerédi, E. (1981), "Sobre el problema del triángulo de Heilbronn", Revista de la Sociedad Matemática de Londres , 24 (3): 385–396, doi : 10.1112 / jlms / s2-24.3.385 , MR 0635870.
- ^ Goldberg, Michael (1972), "Maximizar el triángulo más pequeño formado por n puntos en un cuadrado", Revista de matemáticas , 45 : 135-144, doi : 10.2307 / 2687869 , JSTOR 2687869 , MR 0296816.
- ^ Comellas, Francesc; Yebra, J. Luis A. (2002), "Nuevos límites inferiores para los números de Heilbronn" , Electronic Journal of Combinatorics , 9 (1): R6, MR 1887087.
- ^ Zeng, Zhenbing; Chen, Liangyu (2011), "Sobre la configuración óptima de Heilbronn de siete puntos en el cuadrado", Deducción automatizada en geometría , Lecture Notes in Comput. Sci., 6301 , Heidelberg: Springer, págs. 196-224, doi : 10.1007 / 978-3-642-21046-4_11 , MR 2805061.
- ^ Jiang, Tao; Li, Ming; Vitányi, Paul (2002), "The average-case area of Heilbronn-type triangles", Random Structures & Algorithms , 20 (2): 206–219, arXiv : math / 9902043 , doi : 10.1002 / rsa.10024 , MR 1884433.
- ^ Grimmett, G .; Janson, S. (2003), "Sobre triángulos más pequeños", Estructuras y algoritmos aleatorios , 23 : 206–223.
- ^ Lefmann, Hanno (2008), "Distribuciones de puntos en dimensiones d y puntos simples k grandes ", Geometría discreta y computacional , 40 (3): 401–413, doi : 10.1007 / s00454-007-9041-y , MR 2443292.
enlaces externos
- Weisstein, Eric W. "Problema del triángulo de Heilbronn" . MathWorld .
- Erich's Packing Center , por Erich Friedman, que incluye las soluciones más conocidas al problema de Heilbronn para valores pequeños de n para cuadrados, círculos, triángulos equiláteros y regiones convexas de forma variable pero área fija.