thumb|300px|Seis puntos en el cuadrado unitario, con los triángulos más pequeños (rojos) de área 1/8, el área óptima para este número de puntos. Otros triángulos más grandes están coloreados de azul. Estos puntos son una transformación afín de un hexágono regular, pero para un mayor número 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 colocación de puntos en el plano, evitando triángulos de área pequeña. Lleva el nombre de Hans Heilbronn, quien conjetura que, sin importar cómo se coloquen los puntos en un área dada, el área del triángulo más pequeño será a lo sumo inversamente proporcional al cuadrado del número de puntos. Su conjetura fue refutada, 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 centra en la colocación de puntos dentro de una forma en el plano, como el cuadrado unitario o el disco unitario, para un número dado Cada trío de puntos forma los tres vértices de un triángulo, y entre estos triángulos, el problema se interesa por el triángulo más pequeño, medido por su área. Diferentes disposiciones de puntos tendrán diferentes triángulos más pequeños, y el problema pregunta: ¿cómo deben colocarse puntos para maximizar el área del triángulo más pequeño?

Más formalmente, la forma puede asumirse como un conjunto compacto en el plano, lo que significa que permanece dentro de una distancia acotada desde el origen y que los puntos pueden colocarse en su frontera. En la mayoría de los trabajos sobre este problema, es además un conjunto convexo de área no nula. Cuando tres de los puntos colocados están en una línea, se consideran como formadores de un triángulo degenerado cuya área se define como cero, por lo que las disposiciones que maximizan el triángulo más pequeño no tendrán tríos de puntos colineales. 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 aproximan a la optimalidad. El número puede definirse como el área del triángulo más pequeño en esta colocación óptima. Un ejemplo se muestra en la figura, 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 mayores. Esta es la colocación óptima de seis puntos en un cuadrado unitario: todas las demás colocaciones forman al menos un triángulo con área 1/8 o menor. Por lo tanto,

Aunque los investigadores han estudiado el valor de para formas específicas y números pequeños de puntos, Heilbronn estaba más interesado en 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 Es decir, la pregunta de Heilbronn se refiere a la tasa de crecimiento como función Para dos formas cualesquiera los números y difieren solo por un factor constante, ya que cualquier colocación de puntos dentro de puede escalarse mediante una transformación afín para encajar cambiando el área del triángulo mínimo 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 el subíndice puede

Conjetura de Heilbronn y su refutación Heilbronn conjeturó antes de 1951 que el área del triángulo mínimo siempre se reduce rápidamente como función —más específicamente, inversamente proporcional al cuadrado En términos de la notación O grande, esto puede expresarse como el límite

thumb|upright=0.8|Soluciones al problema de no tres en línea, grandes conjuntos de puntos en una rejilla sin tres puntos colineales, pueden escalarse en un cuadrado unitario con un área de triángulo mínima En la otra dirección, Paul Erdős encontró ejemplos de conjuntos de puntos con un área de triángulo mínima proporcional demostrando que, si es cierta, la conjetura de Heilbronn no podía reforzarse. Erdős formuló el problema de no tres en línea, sobre grandes conjuntos de puntos en una rejilla 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 rejilla entera (para no tienen 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 de al menos Cuando estos puntos de la rejilla se escalan para encajar en un cuadrado unitario, su área de triángulo más pequeña es proporcional coincidiendo con el límite superior conjeturado por Heilbronn. Si no es primo, entonces una construcción similar usando un número primo cercano a logra el mismo límite inferior asintótico.}

finalmente refutaron la conjetura de Heilbronn, utilizando el método probabilístico para encontrar conjuntos de puntos cuya área de triángulo más pequeña es mayor que las encontradas por Erdős. Su construcción involucra los siguientes pasos: Colocar aleatoriamente puntos en el cuadrado unitario, para Eliminar todos los pares de puntos que estén inesperadamente cerca uno del otro. Demostrar que hay 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. Eliminar todos los puntos que pertenezcan a estos ciclos. Aplicar un lema de eliminación de triángulos para hipergrafos uniformes de 3 con alta circunferencia para mostrar que, con alta probabilidad, los puntos restantes incluyen un subconjunto de puntos que no forman triángulos de área pequeña. El área resultante de su construcción crece asintóticamente como

La prueba puede ser desaleatorizada, lo que lleva a un algoritmo de tiempo polinómico para construir colocaciones con esta área de triángulo.

Límites superiores Cada conjunto de puntos en el cuadrado unitario forma un triángulo de área a lo sumo inversamente proporcional Una forma de verlo 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 y elegir los tres puntos consecutivos en este orden cuyas estén más cerca. 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 de la forma

El mejor límite conocido hasta la fecha es de la forma

para alguna demostrado por .

Un nuevo límite superior igual a fue demostrado por .

Formas y números específicos ha investigado las disposiciones óptimas de puntos en un cuadrado, para hasta 16. Las construcciones de Goldberg para hasta seis puntos se encuentran en la frontera del cuadrado y están colocadas para formar una transformación afín de los vértices de un polígono regular. Para valores mayores mejoraron los límites de Goldberg, y para estos valores las soluciones incluyen puntos interiores al cuadrado. Estas construcciones han sido demostradas óptimas para hasta siete puntos. La prueba utilizó una búsqueda computacional 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, que incluye la solución óptima final, su optimalidad fue demostrada usando técnicas de cálculo simbólico.

Las siguientes son las mejores soluciones conocidas para 7–12 puntos en un cuadrado unitario, encontradas mediante recocido simulado; la disposición para siete puntos se sabe que es óptima.

En lugar de buscar colocaciones ó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 para esta forma, con seis puntos colocados óptimamente en los vértices del hexágono. Las formas convexas de área unitaria que maximizan tienen

Variaciones Se han estudiado muchas variaciones de este problema, incluido el caso de un conjunto de puntos distribuidos uniformemente al azar, para el cual 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. También se han estudiado variaciones que involucran el volumen de símplices de dimensiones superiores.

Otra versión de dimensión superior añade otro y pregunta por colocaciones 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 relativos pueden formar formas más complicadas. Cuando es suficientemente grande en relación los conjuntos de puntos colocados aleatoriamente tienen un volumen de envoltura convexa mínimo de No es posible un límite mejor; cualquier colocación tiene puntos con obtenido al elegir algunos puntos consecutivos en orden de coordenadas. Este resultado tiene aplicaciones en estructuras de datos de búsqueda por rangos.

Referencias

Enlaces externos

Centro de empaquetamiento de Erich, por Erich Friedman, incluye las mejores soluciones conocidas para el problema de Heilbronn para valores pequeños de en cuadrados, círculos, triángulos equiláteros y regiones convexas de forma variable pero área fija.

Categoría:Geometría discreta Categoría:Área Categoría:Matemáticas Categoría:Triángulos