Problema del triángulo de Heilbronn

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

Problema sin resolver en matemáticas :

¿Cuál es la tasa de crecimiento asintótico del área del triángulo más pequeño determinado por tres de los 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, con los triángulos más pequeños (rojos) con un área de 1/8, el área óptima para esta cantidad de puntos. Otros triángulos más grandes están coloreados en azul. Estos puntos son una transformación afín de un hexágono regular , pero para una cantidad mayor de puntos la solución óptima no forma un polígono convexo.

En geometría discreta y teoría de discrepancias , el problema del triángulo de Heilbronn es un problema de colocación de puntos en el plano, evitando triángulos de área pequeña . Recibe su nombre en honor a Hans Heilbronn , quien conjeturó que, sin importar cómo se coloquen los puntos en un área dada, el área del triángulo más pequeña será, como máximo, inversamente proporcional al cuadrado del número de puntos. Su conjetura resultó ser 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 colocación de puntos dentro de una figura en el plano, como el cuadrado unitario o el disco unitario , para un número dado . Cada triple de puntos forma los tres vértices de un triángulo y, entre estos triángulos, el problema se refiere al triángulo más pequeño, medido por área. Diferentes colocaciones de puntos darán diferentes triángulos más pequeños y el problema plantea la siguiente 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, es 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 colocaciones que maximizan el triángulo más pequeño no tendrán triples colineales de puntos. La suposición de que la forma es compacta implica que existe una colocación óptima de puntos, en lugar de solo una secuencia de colocaciones que se acercan a la optimalidad. El número puede definirse como el área del triángulo más pequeño en esta colocació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 menor. 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 preocupado en cambio por su comportamiento asintótico : si la forma se mantiene fija, pero varía, ¿cómo varía el área del triángulo más pequeño con ? Es decir, la pregunta de Heilbronn se refiere a la tasa de crecimiento de , como una 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 de puede escalarse mediante una transformación afín para ajustarse 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 de que omiten la constante de proporcionalidad de ese crecimiento, la elección de es irrelevante y se puede omitir el subíndice . ^[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 la 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 encontrar tres puntos en la línea , grandes conjuntos de puntos de la cuadrícula sin tres puntos colineales, se pueden escalar hasta formar 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 triangular mínima proporcional a , ${\displaystyle 1/n^{2}}$ demostrando que, de ser cierto, el límite conjeturado de Heilbronn no podría ser reforzado. Erdős formuló el problema de no-tres en línea , en grandes conjuntos de puntos de la cuadrícula sin tres en una 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, por la fórmula de Pick , cada uno de los triángulos que forman tiene un área de al menos . Cuando estos puntos de la cuadrícula se escalan para encajar dentro de un cuadrado unitario, su área triangular más pequeña es proporcional a , lo que coincide con el límite superior conjeturado de Heilbronn. Si no es primo, entonces una construcción similar que use 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 cuya área triangular más pequeña sea mayor que la encontrada por Erdős. Su construcción implica los siguientes pasos:

• Coloque puntos aleatoriamente en el cuadrado unitario, para algunos . ${\displaystyle n^{1+\varepsilon }}$ ${\displaystyle \varepsilon >0}$
• Elimina todos los pares de puntos que estén inesperadamente cerca unos de otros.
• Demuestre que quedan pocos triángulos de área reducida y, por lo tanto, solo hay un número sublineal de ciclos formados por dos, tres o cuatro triángulos de área reducida. Elimine todos los puntos que pertenecen a estos ciclos.
• Aplique un lema de eliminación de triángulos para hipergrafos 3-uniformes de gran circunferencia para demostrar 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 como ^[5] La prueba se puede desaleatorizar , lo que conduce a un algoritmo de tiempo polinomial para construir ubicaciones con esta á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 la envoltura convexa 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 ordenamiento cuyas coordenadas sean las 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 mejor límite 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, para 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] Se ha demostrado que estas construcciones son óptimas para hasta 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 solución óptima eventual, su optimalidad se demostró utilizando 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 a través de recocido simulado ; ^[3] se sabe que la disposición para 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 dada, se puede buscar una forma óptima para un número dado de puntos. Entre las formas convexas con área uno, el hexágono regular es el que maximiza ; para esta forma, , con seis puntos ubicados óptimamente en los vértices del hexágono. ^[10] Las formas convexas de área unitaria 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 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 variaciones que involucran el volumen de símplices de dimensiones superiores . ^{[14] [15] [16]}

En lugar de considerar los símplices, otra versión de dimensiones superiores añade otro parámetro , ${\displaystyle k}$ y pide ubicaciones de puntos en el hipercubo unitario que maximicen el volumen mínimo de la envoltura convexa de cualquier subconjunto de puntos. Para estos subconjuntos forman símplices pero para valores mayores 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 envoltura convexa de -punto mínimo . No es posible un límite mejor; cualquier ubicación tiene puntos con volumen , obtenido al elegir 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}$

Véase también

• Conjunto de 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 puede demostrar sin cálculo que varios triángulos de área mínima son iguales en área, solo se sombrea uno de ellos.

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), "Maximización del 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. Zeng, 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: 7.º taller internacional, ADG 2008, Shanghái, China, 22-24 de septiembre de 2008, Documentos revisados , Lecture Notes in Computer Science, vol. 6301, Heidelberg: Springer, págs. 196-224, doi :10.1007/978-3-642-21046-4_11, MR  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 más pequeño se volvió más pequeño", Quanta , consultado el 9 de septiembre de 2023
10. Dress, Andreas WM ; Yang, Lu; Zeng, Zhenbing (1995), "Problema de Heilbronn para seis puntos en un cuerpo convexo plano", en Du, Ding-Zhu; Pardalos, Panos M. (eds.), Minimax and Applications , Nonconvex Optim. Appl., vol. 4, Kluwer Acad. Publ., Dordrecht, págs. 173–190, doi :10.1007/978-1-4613-3557-3_13, MR  1376828
11. Yang, Lu; Zeng, Zhenbing (1995), "Problema de Heilbronn para siete puntos en un cuerpo convexo plano", en Du, Ding-Zhu; Pardalos, Panos M. (eds.), Minimax and Applications , Nonconvex Optim. Appl., vol. 4, Kluwer Acad. Publ., Dordrecht, págs. 191–218, doi :10.1007/978-1-4613-3557-3_14, MR  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", Random Structures & Algorithms , 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", SIAM Journal on Discrete Mathematics , 19 (1): 192–195, doi :10.1137/S0895480103435810, MR  2178353 ${\displaystyle d}$
15. Lefmann, Hanno (2008), "Distribuciones de puntos en dimensiones y símplices de puntos grandes", Geometría discreta y computacional , 40 (3): 401–413, doi : 10.1007/s00454-007-9041-y , MR  2443292 ${\displaystyle d}$ ${\displaystyle k}$
16. Barequet, Gill; Naor, Jonathan (2006), " Símplices -D grandes en el cubo unitario dimensional", Far East Journal of Applied Mathematics , 24 (3): 343–354, MR  2283483 ${\displaystyle k}$ ${\displaystyle d}$
17. Chazelle, Bernard (2001), El método de la discrepancia: aleatoriedad y complejidad, Cambridge University Press, pág. 266, ISBN 978-0-521-00357-5

Enlaces externos

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