Problema del triángulo de Heilbronn

En conjuntos de puntos sin triángulos de área pequeña

Problema no resuelto en matemáticas :

¿Cuál es la tasa de crecimiento asintótico del área del triángulo más pequeño determinada por tres puntos de un cuadrado, cuando los puntos se eligen para maximizar esta área? ${\displaystyle n}$

(más problemas sin resolver en matemáticas)

Seis puntos en el cuadrado unitario, y los triángulos más pequeños (rojos) tienen un área de 1/8, el área óptima para esta cantidad de puntos. Otros triángulos más grandes son de color azul. Estos puntos son una transformación afín de un hexágono regular , pero para un número mayor de puntos la solución óptima no forma un polígono convexo.

En geometría discreta y teoría de la discrepancia , el problema del triángulo de Heilbronn es un problema de colocar puntos en el plano, evitando triángulos de área pequeña . Lleva el nombre de Hans Heilbronn , quien conjeturó que, no importa cómo se coloquen los puntos en un área determinada, el área del triángulo más pequeño será como máximo inversamente proporcional al cuadrado del número de puntos. Se demostró que su conjetura era falsa, pero la tasa de crecimiento asintótico del área mínima del triángulo sigue siendo desconocida.

Definición

El problema del triángulo de Heilbronn se refiere a la ubicación de puntos dentro de una forma en el plano, como el cuadrado unitario o el disco unitario , para un número determinado . Cada tripleta de puntos forma los tres vértices de un triángulo , y entre estos triángulos, el problema concierne al triángulo más pequeño, medido en área. Diferentes ubicaciones de puntos tendrán diferentes triángulos más pequeños, y el problema pregunta: ¿cómo se deben colocar los puntos para maximizar el área del triángulo más pequeño? ^[1] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

Más formalmente, se puede suponer que la forma es un conjunto compacto en el plano, lo que significa que permanece dentro de una distancia limitada desde el origen y que se permite colocar puntos en su límite. En la mayoría de los trabajos sobre este problema, hay además un conjunto convexo de área distinta de cero. Cuando tres de los puntos colocados se encuentran en una línea , se considera que forman un triángulo degenerado cuya área se define como cero, por lo que las ubicaciones que maximizan el triángulo más pequeño no tendrán tripletas colineales de puntos. La suposición de que la forma es compacta implica que existe una ubicación óptima de los puntos, en lugar de sólo una secuencia de ubicaciones que se acercan a la óptima. El número puede definirse como el área del triángulo más pequeño en esta ubicación óptima. ^{[1] [a]} En la figura se muestra un ejemplo, con seis puntos en un cuadrado unitario. Estos seis puntos forman triángulos diferentes, cuatro de los cuales están sombreados en la figura. Seis de estos 20 triángulos, con dos de las formas sombreadas, tienen un área de 1/8; los 14 triángulos restantes tienen áreas más grandes. Esta es la ubicación óptima de seis puntos en un cuadrado unitario: todas las demás ubicaciones forman al menos un triángulo con un área de 1/8 o menos. Por lo tanto, . ^[2] ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle n}$ ${\displaystyle \Delta _{D}(n)}$ ${\displaystyle {\tbinom {6}{3}}=20}$ ${\displaystyle \Delta _{D}(6)={\tfrac {1}{8}}}$

Aunque los investigadores han estudiado el valor de para formas específicas y números pequeños específicos de puntos, ^{[2] [3] [4]} Heilbronn estaba más bien preocupado por su comportamiento asintótico : si la forma se mantiene fija, pero varía, ¿cómo cambia el área de ¿El triángulo más pequeño varía con ? Es decir, la pregunta de Heilbronn se refiere a la tasa de crecimiento de , en función de . Para dos formas cualesquiera y , los números y difieren solo por un factor constante, ya que cualquier ubicación de puntos dentro se puede escalar mediante una transformación afín para que quepa dentro de , cambiando el área mínima del triángulo solo por una constante. Por lo tanto, en los límites de la tasa de crecimiento que omiten la constante de proporcionalidad de ese crecimiento, la elección de es irrelevante y el subíndice puede omitirse. ^[1] ${\displaystyle \Delta _{D}(n)}$ ${\displaystyle D}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \Delta _{D}(n)}$ ${\displaystyle n}$ ${\displaystyle D}$ ${\displaystyle D'}$ ${\displaystyle \Delta _{D}(n)}$ ${\displaystyle \Delta _{D'}(n)}$ ${\displaystyle n}$ ${\displaystyle D}$ ${\displaystyle D'}$ ${\displaystyle \Delta _{D}(n)}$ ${\displaystyle D}$

La conjetura de Heilbronn y su refutación.

Heilbronn conjeturó antes de 1951 que el área mínima del triángulo siempre se contrae rápidamente en función de ${\displaystyle n}$ (más específicamente, inversamente proporcional al cuadrado de) . ^{[1] [b]} ${\displaystyle n}$ En términos de notación O grande , esto se puede expresar como el límite $${\displaystyle \Delta (n)=O\left({\frac {1}{n^{2}}}\right).}$$

Las soluciones al problema de no tener tres en línea , grandes conjuntos de puntos de cuadrícula sin tres puntos colineales, se pueden escalar a un cuadrado unitario con un área de triángulo mínima . ${\displaystyle \Omega (1/n^{2})}$

En la otra dirección, Paul Erdős encontró ejemplos de conjuntos de puntos con un área mínima de triángulo proporcional a , ${\displaystyle 1/n^{2}}$ lo que demuestra que, de ser cierto, el límite conjeturado de Heilbronn no podría reforzarse. Erdős formuló el problema de los tres en línea , en grandes conjuntos de puntos de la cuadrícula sin tres en línea, para describir estos ejemplos. Como observó Erdős, cuando es un número primo , el conjunto de puntos en una cuadrícula de números enteros (para ) no tiene tres puntos colineales y, por lo tanto, según la fórmula de Pick, cada uno de los triángulos que forman tiene un área al menos . Cuando estos puntos de la cuadrícula se escalan para caber dentro de un cuadrado unitario, su área de triángulo más pequeña es proporcional a , coincidiendo con el límite superior conjeturado por Heilbronn. Si no es primo, entonces una construcción similar que utilice un número primo cercano a logra el mismo límite inferior asintótico. ^{[1] [c]} ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle (i,i^{2}{\bmod {n}})}$ ${\displaystyle n\times n}$ ${\displaystyle 0\leq i<n}$ ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle 1/n^{2}}$ ${\displaystyle n}$ ${\displaystyle n}$

Komlós, Pintz y Szemerédi (1982) finalmente refutaron la conjetura de Heilbronn, utilizando el método probabilístico para encontrar conjuntos de puntos cuyo área de triángulo más pequeña sea mayor que los encontrados por Erdős. Su construcción implica los siguientes pasos:

• Coloque puntos al azar en el cuadrado unitario, para algunos . ${\displaystyle n^{1+\varepsilon }}$ ${\displaystyle \varepsilon >0}$
• Elimine todos los pares de puntos que inesperadamente estén muy juntos.
• Demuestre que quedan pocos triángulos de área baja y, por lo tanto, solo un número sublineal de ciclos formados por dos, tres o cuatro triángulos de área baja. Elimine todos los puntos pertenecientes a estos ciclos.
• Aplique un lema de eliminación de triángulos para hipergráficos de 3 uniformes de gran circunferencia para mostrar que, con alta probabilidad, los puntos restantes incluyen un subconjunto de puntos que no forman ningún triángulo de área pequeña. ${\displaystyle n}$

El área resultante de su construcción crece asintóticamente a medida que ^[5] La prueba se puede desaleatorizar , lo que lleva a un algoritmo de tiempo polinomial para construir ubicaciones con este área de triángulo. ^[6] $${\displaystyle \Delta (n)=\Omega \left({\frac {\log n}{n^{2}}}\right).}$$

Límites superiores

Cada conjunto de puntos en el cuadrado unitario forma un triángulo de área como máximo inversamente proporcional a . Una forma de ver esto es triangular el casco convexo del conjunto de puntos dado y elegir el más pequeño de los triángulos en la triangulación. Otra es ordenar los puntos por sus coordenadas y elegir los tres puntos consecutivos en este orden cuyas coordenadas estén más cercanas entre sí. En el primer artículo publicado sobre el problema del triángulo de Heilbronn, en 1951, Klaus Roth demostró un límite superior más fuerte en , de la forma ^[1] El límite mejor conocido hasta la fecha es de la forma para alguna constante , demostrado por Komlós, Pintz y Szemerédi (1981). ^[7] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle \Delta (n)}$ $${\displaystyle \Delta (n)=O\left({\frac {1}{n{\sqrt {\log \log n}}}}\right).}$$ $${\displaystyle \Delta (n)\leq {\frac {\exp {\left(c{\sqrt {\log n}}\right)}}{n^{8/7}}},}$$ ${\displaystyle c}$

Cohen, Pohoata y Zakharov (2023) demostraron un nuevo límite superior igual a . ^{[8] [9]} ${\displaystyle n^{-{\frac {8}{7}}-{\frac {1}{2000}}}}$

Formas y números específicos.

Goldberg (1972) ha investigado las disposiciones óptimas de los puntos en un cuadrado, hasta 16. ^[2] 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 los vértices de un polígono regular . Para valores mayores de , Comellas y Yebra (2002) mejoraron los límites de Goldberg, y para estos valores las soluciones incluyen puntos interiores al cuadrado. ^[3] Estas construcciones han demostrado ser óptimas hasta en siete puntos. La prueba utilizó una búsqueda por computadora para subdividir el espacio de configuración de posibles disposiciones de los puntos en 226 subproblemas diferentes, y utilizó técnicas de programación no lineal para mostrar que en 225 de esos casos, la mejor disposición no era tan buena como el límite conocido. En el caso restante, incluida la eventual solución óptima, su optimización se demostró mediante técnicas de cálculo simbólico . ^[4] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

Las siguientes son las soluciones más conocidas para 7 a 12 puntos en un cuadrado unitario, encontradas mediante recocido simulado ; ^[3] Se sabe que la disposición de siete puntos es óptima. ^[4]

• 
  7 puntos en un cuadrado, los 8 triángulos mínimos sombreados ( ) ${\displaystyle A\approx 0.0839}$
• 
  8 puntos en un cuadrado, 5 de 12 triángulos mínimos sombreados ^[d] ( ) ${\displaystyle A\approx 0.0724}$
• 
  9 puntos en un cuadrado, 6 de 11 triángulos mínimos sombreados ^[d] ( ) ${\displaystyle A\approx 0.0549}$
• 
  10 puntos en un cuadrado, 3 de 16 triángulos mínimos sombreados ^[d] ( ) ${\displaystyle A\approx 0.0465}$
• 
  11 puntos en un cuadrado, 8 de 28 triángulos mínimos sombreados ^[d] ( ) ${\displaystyle A\approx 0.0370}$
• 
  12 puntos en un cuadrado, 3 de 20 triángulos mínimos sombreados ^[d] ( ) ${\displaystyle A\approx 0.0326}$

En lugar de buscar ubicaciones óptimas para una forma determinada, se puede buscar una forma óptima para un número determinado de puntos. Entre las formas convexas con área uno, el hexágono regular es el que maximiza ; para esta forma, con seis puntos ubicados de manera óptima en los vértices del hexágono. ^[10] Las formas convexas de unidad de área que maximizan tienen . ^[11] ${\displaystyle D}$ ${\displaystyle \Delta _{D}(6)}$ ${\displaystyle \Delta _{D}(6)={\tfrac {1}{6}}}$ ${\displaystyle \Delta _{D}(7)}$ ${\displaystyle \Delta _{D}(7)={\tfrac {1}{9}}}$

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 en la aproximación de Poisson muestran que el valor esperado del área mínima es inversamente proporcional al cubo del número de puntos. . ^{[12] [13]} También se han estudiado las variaciones que involucran el volumen de simples de dimensiones superiores . ^{[14] [15] [16]}

En lugar de considerar simples, otra versión de dimensiones superiores agrega otro parámetro y ${\displaystyle k}$ solicita ubicaciones de puntos en el hipercubo unitario que maximicen el volumen mínimo del casco convexo de cualquier subconjunto de puntos. Estos subconjuntos forman simples, pero para valores más grandes de , en relación con , pueden formar formas más complicadas. Cuando es suficientemente grande en relación con , los conjuntos de puntos colocados aleatoriamente tienen un volumen de casco convexo de punto mínimo . No es posible un límite mejor; cualquier ubicación tiene puntos con volumen , obtenidos eligiendo algunos puntos consecutivos en orden de coordenadas. Este resultado tiene aplicaciones en estructuras de datos de búsqueda de rango . ^[17] ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k=d+1}$ ${\displaystyle k}$ ${\displaystyle d}$ ${\displaystyle k}$ ${\displaystyle \log n}$ ${\displaystyle k}$ ${\displaystyle \Omega (k/n)}$ ${\displaystyle k}$ ${\displaystyle O(k/n)}$ ${\displaystyle k}$

Ver también

• Conjunto Danzer , un conjunto de puntos que evita triángulos vacíos de gran área.

Notas

1. La definición de Roth utiliza una notación ligeramente diferente y normaliza el área del triángulo dividiéndolo por el área de . ${\displaystyle D}$
2. La conjetura se atribuye a Heilbronn en Roth (1951), pero sin citar ninguna publicación específica.
3. La construcción de Erdős se publicó en Roth (1951), acreditada a Erdős.
4. Cuando se pueden mostrar varios triángulos de área mínima sin calcular que tienen el mismo área, solo uno de ellos está sombreado.

Referencias

1. 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
2. Goldberg, Michael (1972), "Maximizar el triángulo más pequeño formado por puntos en un cuadrado", Mathematics Magazine , 45 (3): 135–144, doi :10.2307/2687869, JSTOR  2687869, MR  0296816 ${\displaystyle n}$
3. Comellas, Francesc; Yebra, J. Luis A. (2002), "Nuevos límites inferiores para los números de Heilbronn", Electronic Journal of Combinatorics , 9 (1): R6, doi : 10.37236/1623 , MR  1887087
4. , Zhenbing; Chen, Liangyu (2011), "Sobre la configuración óptima de Heilbronn de siete puntos en el cuadrado", en Sturm, Thomas; Zengler, Christoph (eds.), Deducción automatizada en geometría: séptimo taller internacional, ADG 2008, Shanghai, China, 22 al 24 de septiembre de 2008, artículos revisados , Lecture Notes in Computer Science, vol. 6301, Heidelberg: Springer, págs. 196–224, doi :10.1007/978-3-642-21046-4_11, SEÑOR  2805061
5. Komlós, J .; Pintz, J .; Szemerédi, E. (1982), "Un límite inferior para el problema de Heilbronn", Revista de la Sociedad Matemática de Londres , 25 (1): 13–24, doi :10.1112/jlms/s2-25.1.13, SEÑOR  0645860
6. Bertram-Kretzberg, Claudia; Hofmeister, Thomas; Lefmann, Hanno (2000), "Un algoritmo para el problema de Heilbronn", SIAM Journal on Computing , 30 (2): 383–390, doi :10.1137/S0097539798348870, hdl : 2003/5313 , MR  1769363
7. 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, SEÑOR  0635870
8. Cohen, Alex; Pohoata, Cosmin; Zakharov, Dmitrii (2023), "Un nuevo límite superior para el problema del triángulo de Heilbronn", arXiv : 2305.18253 [math.CO]
9. Sloman, Leila (8 de septiembre de 2023), "El triángulo más grande y pequeño se hizo más pequeño", Quanta , consultado el 9 de septiembre de 2023
10. Vestido, Andreas WM ; Yang, Lu; Zeng, Zhenbing (1995), "Problema de Heilbronn para seis puntos en un cuerpo plano convexo", en Du, Ding-Zhu; Pardalos, Panos M. (eds.), Minimax y Aplicaciones , Optim no convexo. Aplicación, vol. 4, Kluwer Acad. Publ., Dordrecht, págs. 173–190, doi :10.1007/978-1-4613-3557-3_13, SEÑOR  1376828
11. Yang, Lu; Zeng, Zhenbing (1995), "Problema de Heilbronn para siete puntos en un cuerpo plano convexo", en Du, Ding-Zhu; Pardalos, Panos M. (eds.), Minimax y Aplicaciones , Optim no convexo. Aplicación, vol. 4, Kluwer Acad. Publ., Dordrecht, págs. 191–218, doi :10.1007/978-1-4613-3557-3_14, SEÑOR  1376829
12. Jiang, Tao; Li, Ming ; Vitányi, Paul (2002), "El área promedio de los triángulos tipo Heilbronn", Estructuras y algoritmos aleatorios , 20 (2): 206–219, arXiv : math/9902043 , doi :10.1002/rsa.10024, MR  1884433 , S2CID  2079746
13. Grimmett, G .; Janson, S. (2003), "Sobre los triángulos más pequeños", Algoritmos y estructuras aleatorias , 23 (2): 206–223, doi :10.1002/rsa.10092, S2CID  12272636
14. Brass, Peter (2005), "Un límite superior para el análogo dimensional del problema del triángulo de Heilbronn", Revista SIAM de Matemáticas Discretas , 19 (1): 192–195, doi :10.1137/S0895480103435810, MR  2178353 ${\displaystyle d}$
15. Lefmann, Hanno (2008), "Distribuciones de puntos en dimensiones y simples de puntos grandes", Geometría computacional y discreta , 40 (3): 401–413, doi : 10.1007/s00454-007-9041-y , MR  2443292 ${\displaystyle d}$ ${\displaystyle k}$
16. Bareket, Gill; Naor, Jonathan (2006), " Simplices -D grandes en el cubo unitario -dimensional", Far East Journal of Applied Mathematics , 24 (3): 343–354, SEÑOR  2283483 ${\displaystyle k}$ ${\displaystyle d}$
17. Chazelle, Bernard (2001), El método de la discrepancia: aleatoriedad y complejidad, Cambridge University Press, p. 266, ISBN 978-0-521-00357-5

enlaces externos

• Weisstein, Eric W. , "Problema del triángulo de Heilbronn", MathWorld
• Erich's Packing Center, de Erich Friedman, que incluye las soluciones más conocidas al problema de Heilbronn para valores pequeños de cuadrados, círculos, triángulos equiláteros y regiones convexas de forma variable pero área fija. ${\displaystyle n}$