From Computational Certification to Exact Coordinates: Heilbronn's Triangle Problem on the Unit Square Using Mixed-Integer Optimization

Each language version is independently generated for its own context, not a direct translation.

Imagina que tienes una habitación cuadrada perfecta (un metro por metro) y quieres colocar n personas dentro de ella. Tu misión es muy específica: colocar a estas personas de tal manera que, si eliges a cualquier grupo de tres de ellas para formar un triángulo, el triángulo más pequeño posible sea lo más grande posible.

Suena un poco como un juego de lógica, ¿verdad? A este rompecabezas matemático se le llama El Problema del Triángulo de Heilbronn.

Durante décadas, los matemáticos han luchado con esto. Para tener pocos puntos (como 5 o 6), era fácil. Pero cuando llegabas a 9 personas, el problema se volvía tan complejo que incluso las supercomputadoras tardaban días enteros en encontrar la solución perfecta, y a veces ni siquiera estaban seguros de si era la mejor posible.

Aquí es donde entra este nuevo artículo, escrito por Nathan Sudermann-Merx. Vamos a explicar su trabajo como si fuera una receta de cocina de dos pasos, usando analogías sencillas.

1. El Problema: "El Juego de las Sillas Vacías"

Imagina que estás organizando una fiesta en una sala cuadrada. Quieres que nadie se sienta "atrapado" en un rincón muy pequeño. Si tres invitados forman un triángulo muy pequeño, significa que están demasiado juntos. Quieres maximizar el tamaño del triángulo más pequeño entre todos los posibles grupos de tres.

El problema es que hay demasiadas formas de colocar a las personas. Puedes rotar la sala, girar a las personas, o intercambiar sus nombres, y seguirás teniendo la misma configuración geométrica. Es como intentar encontrar una aguja en un pajar, pero el pajar tiene millones de agujas idénticas.

2. La Solución: "La Estrategia de la Cocina de Dos Pasos"

El autor propone una metodología brillante llamada "Optimizar y luego Refinar". Piénsalo así:

Paso 1: El "Bosquejo Rápido" (Optimización Numérica)

Primero, usamos un supercomputador (un solver de optimización) para hacer un "boceto" rápido.

El truco de la simetría: El autor descubrió una regla de oro: en la solución perfecta, siempre hay al menos cinco personas pegadas a las paredes de la sala.
Rompiendo el hielo: En lugar de dejar que la computadora pruebe millones de formas de rotar la sala, el autor le dice: "Oye, vamos a asumir que estas cinco personas específicas están pegadas a las esquinas y paredes de esta manera exacta".
El resultado: Esto reduce el "pajar" de agujas a solo una aguja. Gracias a este truco, la computadora encuentra la solución numérica para 9 personas en 15 minutos en una computadora normal, en lugar de los días que tardaban antes.

Es como si, en lugar de buscar una llave perdida en todo el jardín, supieras con certeza que está bajo la maceta del porche. ¡Basta de buscar en el césped!

Paso 2: El "Toque de Magia Exacta" (Refinamiento Simbólico)

El primer paso te da coordenadas numéricas aproximadas (ej: 0.7127...). Pero en matemáticas puras, queremos la respuesta exacta, como una fórmula con raíces cuadradas, no un número redondeado.

Aquí entra la segunda parte: el autor toma ese "boceto" numérico y le dice a un software de álgebra: "Sabemos que estos puntos forman triángulos de igual tamaño. Resuelve las ecuaciones exactas basadas en esa forma".
El software descubre que las coordenadas no son números aleatorios, sino fórmulas elegantes que involucran raíces cuadradas (como $\sqrt{65}$ ).

La analogía: Es como si el primer paso te dijera: "El tesoro está a 100 metros al norte". El segundo paso es usar un mapa de alta precisión para decirte: "El tesoro está exactamente bajo la piedra con la inscripción 'X' a 100 metros y 3 centímetros al norte".

3. ¿Qué descubrieron? (Las Sorpresas)

Al encontrar las soluciones exactas para 5, 6, 7, 8 y 9 personas, descubrieron patrones fascinantes:

El "Agrupamiento" (Clustering): No solo importa el triángulo más pequeño. Descubrieron que los otros triángulos (los que no son los más pequeños) tienden a agruparse en unos pocos tamaños específicos. Es como si la naturaleza dijera: "No hagas triángulos de todos los tamaños posibles; haz solo unos cuantos tamaños estándar". Esto sugiere que hay una estructura oculta y rígida en cómo se organizan estos puntos.
Confirmación: Confirmaron que la solución que otros encontraron en 2002 para 9 personas era, de hecho, la mejor posible, algo que nadie había podido probar matemáticamente hasta ahora.

4. ¿Por qué es importante?

Antes, resolver esto era como intentar adivinar el código de una caja fuerte probando millones de combinaciones. Ahora, el autor nos ha dado:

Una llave maestra: Una forma de reducir el problema eliminando las opciones redundantes (la simetría).
Un mapa exacto: Las coordenadas matemáticas precisas, no solo aproximaciones.

Esto es como pasar de tener un mapa dibujado a mano con manchas de café a tener un plano arquitectónico digital perfecto. Además, han puesto todo el código y los datos en internet para que cualquiera pueda verificarlo, asegurando que la ciencia sea transparente y reproducible.

En resumen: Este paper toma un problema geométrico antiguo y difícil, le aplica un "truco de simetría" para hacerlo manejable para una computadora común, y luego usa magia algebraica para obtener la respuesta exacta y elegante, revelando patrones ocultos en la forma en que los puntos se organizan en el espacio.

Each language version is independently generated for its own context, not a direct translation.

Aquí tienes un resumen técnico detallado del artículo en español, estructurado según los puntos solicitados:

Título: De la Certificación Computacional a Coordenadas Exactas: El Problema del Triángulo de Heilbronn en el Cuadrado Unitario mediante Optimización Entera Mixta

Autor: Nathan Sudermann-Merx
Fecha: 13 de marzo de 2026

1. El Problema

El Problema del Triángulo de Heilbronn es un problema clásico de geometría discreta que plantea la siguiente cuestión:

¿Cómo deben colocarse $n$ puntos en un cuadrado unitario $[0, 1]^2$ para que el área del triángulo más pequeño formado por cualquier tripleta de estos puntos sea lo más grande posible?

El objetivo es encontrar la configuración óptima que maximice el área mínima $\Delta_n$ . Aunque se han establecido cotas asintóticas (tanto superiores como inferiores) para grandes valores de $n$ , el problema para valores pequeños de $n$ (especialmente $n \le 16$ ) ha requerido esfuerzos computacionales masivos y, a menudo, solo se han obtenido soluciones numéricas o aproximadas sin una prueba de optimalidad global rigurosa o coordenadas exactas cerradas.

2. Metodología: Marco "Optimizar-Posteriormente-Afinar" (Optimize-then-Refine)

El artículo propone un marco de trabajo innovador que integra la Programación No Lineal Entera Mixta (MINLP) global con el cálculo simbólico exacto. El proceso se divide en dos etapas principales:

Etapa 1: Certificación Computacional Global

Modelo de Optimización: Se formula el problema como un MINLP. La función objetivo es maximizar $z$ , sujeto a que $z \le |A_t|$ para todo triángulo $t$ , donde $A_t$ es el área calculada mediante el determinante de la fórmula de la "cordillera" (shoelace formula).
Estrategia de Rompimiento de Simetría (Clave): El mayor obstáculo computacional es la simetría masiva (grupos diédricos $D_4$ $D_{4}$ y permutaciones $S_n$ $S_{n}$ ). Los autores desarrollan una estrategia basada en la estructura de la frontera de las configuraciones óptimas:
- Demuestran que al menos 5 vértices del casco convexo de la configuración óptima deben estar en la frontera del cuadrado.
- Fijan explícitamente las coordenadas de 5 puntos en los bordes (izquierda, abajo, derecha, arriba) en un orden antihorario.
- Ordenan los puntos interiores por coordenada $x$ .
- Esto elimina millones de ramas equivalentes en el árbol de búsqueda.
Fijación de Signos: Gracias a la estructura de frontera fijada, se pueden determinar de antemano los signos de los determinantes de ciertos triángulos, eliminando variables binarias adicionales.
Resolución: Se utiliza el solver comercial Gurobi para encontrar una solución numérica globalmente óptima y certificar que no existen soluciones mejores (coincidencia de cotas primales y duales).

Etapa 2: Refinamiento Analítico Exacto

Una vez obtenida la solución numérica, se identifican los triángulos críticos (aquellos con el área mínima) y los puntos en la frontera.
Se construye un sistema de ecuaciones polinómicas no lineales imponiendo que las áreas de los triángulos críticos sean iguales.
Se resuelve este sistema utilizando álgebra computacional (SymPy) mediante:
- Solución simbólica directa (para $n$ pequeños).
- Bases de Gröbner (para $n=7$ ).
- Refinamiento numérico-simbólico (para $n=9$ , identificando el campo numérico subyacente, ej. $\mathbb{Q}(\sqrt{65})$ ).
El resultado final son coordenadas exactas (en forma cerrada) para la configuración óptima.

3. Contribuciones Clave

Formulación MINLP más fuerte: La estrategia de rompimiento de simetría basada en la estructura de la frontera y la fijación de signos reduce drásticamente la complejidad computacional.
Eficiencia Computacional: El problema para $n=9$ , que anteriormente requería días de cómputo en clústeres (CPU/GPU), se resuelve a optimalidad global certificada en aproximadamente 15 minutos en un ordenador de escritorio estándar.
Prueba de Optimalidad y Coordenadas Exactas:
- Se proporciona la primera prueba de que la configuración descubierta por Comellas y Yebra (2002) para $n=9$ es globalmente óptima.
- Se derivan coordenadas exactas cerradas para todos los casos óptimos de $n = 5, \dots, 9$ , confirmando resultados anteriores y simplificando sus expresiones algebraicas.
Observaciones Estructurales: Se documentan patrones geométricos, como el agrupamiento de áreas de triángulos no críticos en un número pequeño de valores distintos.
Reproducibilidad: Todo el código, datos y configuraciones están disponibles públicamente en un repositorio de GitHub.

4. Resultados Principales

Rendimiento: Mejora de más de un orden de magnitud respecto a trabajos previos (como el de Monji et al., 2025) para $n=9$ .
Soluciones Exactas:
- $n=5$ : $\Delta_5 = \sqrt{3}/9$ .
- $n=6$ : $\Delta_6 = 1/8$ (con una familia de soluciones de un parámetro).
- $n=7$ : $\Delta_7 \approx 0.083859$ , expresado mediante la raíz de un polinomio cúbico irreducible.
- $n=8$ : $\Delta_8 = (\sqrt{13}-1)/36$ .
- $n=9$ : $\Delta_9 = (-11 + 9\sqrt{65})/320$ . Se confirma la optimalidad de la configuración de Comellas-Yebra.
Comparación: La formulación propuesta es más compacta que la de trabajos concurrentes, ya que evita el uso de constantes "Big-M", variables auxiliares excesivas y pre-procesamiento basado en heurísticas no probadas.

5. Significado e Impacto

Avance en Geometría Computacional: Demuestra que los solucionadores MINLP modernos, combinados con estrategias de modelado inteligentes, pueden resolver problemas de geometría discreta que antes se consideraban intratables o requerían métodos ad-hoc extremadamente complejos.
Puente entre Numerical y Symbolic: El marco "Optimize-then-Refine" ofrece una metodología robusta para obtener pruebas de optimalidad y soluciones exactas en problemas donde las soluciones involucran números algebraicos de grado moderado.
Nuevas Preguntas de Investigación:
- ¿Existe una cota inferior no trivial para el número de triángulos críticos en función de $n$ ?
- ¿Por qué las áreas de los triángulos no críticos se agrupan en valores discretos (fenómeno de "clustering")? Esto sugiere una rigidez estructural oculta en las configuraciones extremas.
Reproducibilidad: Al publicar las configuraciones exactas y el código, se establece una base sólida para futuras investigaciones, eliminando la dependencia de comunicaciones personales para verificar registros en problemas de empaquetado geométrico.

En resumen, el artículo representa un hito en la resolución exacta del Problema de Heilbronn para valores pequeños de $n$ , combinando la potencia de la optimización global con la precisión del álgebra computacional.