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

Este artigo apresenta um novo framework de otimização que combina programação não linear mista-inteira com computação simbólica exata para resolver o problema do triângulo de Heilbronn no quadrado unitário, provando a otimalidade global da configuração para $n=9$ e derivando coordenadas exatas para $n=5$ a $9$ com uma eficiência significativamente superior aos métodos anteriores.

O essencial

Imagine que você tem um quadrado perfeito, como um tabuleiro de xadrez ou uma janela quadrada, e precisa colocar n pontos (pense neles como pregos) dentro dele.

O desafio, conhecido como o Problema do Triângulo de Heilbronn, é: onde você deve colocar esses pregos para garantir que o menor triângulo formado por qualquer três deles seja o maior possível?

Parece simples, mas é um quebra-cabeça matemático antigo e muito difícil. Se você colocar os pontos de qualquer jeito, é fácil formar um triângulo minúsculo e "espremido". O objetivo é espalhar os pontos de forma tão inteligente que, não importa quais três você escolha, o triângulo resultante seja o mais "gordo" e espaçoso possível.

Este artigo de 2026 (um trabalho futuro hipotético, mas baseado em técnicas reais) conta a história de como os autores resolveram esse mistério para casos específicos (de 5 a 9 pontos) de uma forma muito mais rápida e precisa do que nunca antes.

Aqui está a explicação do que eles fizeram, usando analogias do dia a dia:

1. O Problema: Encontrar o "Melhor Espalhamento"

Pense em tentar organizar convidados em uma festa quadrada. Você quer que ninguém fique tão perto de dois outros convidados a ponto de formar um "triângulo de conversa" minúsculo. Você quer que todos os triângulos possíveis sejam grandes.

Por décadas, matemáticos tentaram adivinhar a melhor posição para esses pontos. Para 9 pontos, a melhor tentativa conhecida foi feita em 2002, mas ninguém conseguia provar com 100% de certeza que era a melhor possível. Era como tentar adivinhar a combinação de um cofre: você acha que acertou, mas não tem a prova matemática de que não existe uma combinação melhor.

2. A Solução: O "Detective Matemático" (Otimização)

Os autores criaram um novo método em duas etapas, que chamam de "Otimizar e depois Refinar".

Etapa 1: O Computador como um "Super-Gamer"

Eles usaram um computador poderoso e um software inteligente (otimização mista-inteira) para jogar esse jogo de colocar pontos.

• O Truque do Espelho (Quebra de Simetria): Imagine que você tem um tabuleiro de xadrez. Se você girar o tabuleiro 90 graus ou olhar no espelho, a configuração de pontos parece a mesma, mas para o computador, são milhões de situações diferentes. Isso deixa o computador lento, como se ele estivesse tentando resolver o mesmo quebra-cabeça milhões de vezes.
  • Os autores inventaram uma regra inteligente: "Vamos forçar o primeiro ponto a ficar na borda esquerda, o segundo no fundo, etc." Isso é como dizer ao computador: "Não gaste tempo girando o tabuleiro; vamos olhar apenas para uma posição específica". Isso reduziu o tempo de cálculo de um dia inteiro para apenas 15 minutos em um computador comum!

Etapa 2: O "Alquimista" (Cálculo Simbólico)

O computador da Etapa 1 deu uma resposta numérica (ex: o ponto está em 0.7127...). Mas na matemática pura, queremos a resposta exata, como $\sqrt{2}$ ou $\frac{1}{3}$, e não um número arredondado.

• A Etapa 2 pega essa resposta aproximada do computador e usa um "alquimista" (software de álgebra simbólica) para descobrir a fórmula exata por trás daquele número.
• Eles olharam para os triângulos que estavam "quase" do mesmo tamanho (os críticos) e disseram: "Se esses triângulos são iguais, vamos montar uma equação matemática exata para eles".
• O resultado? Eles conseguiram escrever a posição exata de cada ponto usando fórmulas matemáticas limpas, provando que a configuração encontrada em 2002 era, de fato, a melhor possível.

3. O Que Eles Descobriram (As Surpresas)

Ao olhar para as soluções perfeitas para 5, 6, 7, 8 e 9 pontos, eles notaram padrões curiosos:

• A "Festa de Bordas": Em todas as soluções ótimas, pelo menos 5 pontos estão colados nas bordas do quadrado. É como se os pontos quisessem ficar nas paredes da sala para ter mais espaço no meio.
• A "Agrupação de Tamanhos": Eles notaram algo estranho e bonito. Os triângulos que não são os menores (os que sobram) não têm tamanhos aleatórios. Eles se agrupam em poucos tamanhos específicos. É como se, na festa, todos os grupos de três pessoas (que não formam o menor triângulo) estivessem conversando em grupos de tamanhos padronizados. Isso sugere que a geometria desses pontos é muito mais rígida e organizada do que imaginávamos.

4. Por que isso importa?

• Prova Definitiva: Eles provaram matematicamente que a melhor configuração para 9 pontos é a que todos usavam desde 2002.
• Velocidade: Eles mostraram que, com as técnicas certas, problemas que antes levavam meses de supercomputadores podem ser resolvidos em minutos em um laptop.
• Novas Perguntas: A descoberta de que os triângulos "sobrantes" se agrupam em tamanhos específicos abre um novo campo de pesquisa. Por que a natureza (ou a matemática) gosta de organizar esses pontos dessa maneira?

Resumo em uma frase

Os autores criaram um método inteligente que primeiro usa um computador rápido para encontrar o "quase perfeito" e depois usa matemática pura para transformar esse "quase" em uma resposta exata e perfeita, provando que a melhor maneira de espalhar pontos em um quadrado é mais organizada e simétrica do que pensávamos.

Resumo técnico

Resumo Técnico: O Problema do Triângulo de Heilbronn via Otimização Mista-Inteira

1. O Problema

O Problema do Triângulo de Heilbronn é um clássico problema de geometria discreta que questiona: Como posicionar $n$ pontos dentro de um quadrado unitário de modo que a área do menor triângulo formado por qualquer três desses pontos seja maximizada?
O objetivo é encontrar a configuração ótima que maximize essa área mínima, denotada por $\Delta_n$. Embora existam limites assintóticos conhecidos para $n$ grande, a determinação exata de $\Delta_n$ e das coordenadas dos pontos para valores pequenos de $n$ (especialmente $n \ge 7$) tem sido um desafio computacional significativo, exigindo frequentemente dias de processamento em clusters de CPU/GPU.

2. Metodologia Proposta

Os autores desenvolvem um framework inovador de "Otimizar e Refinar" (Optimize-then-Refine) que integra Programação Não Linear Mista-Inteira (MINLP) global com computação simbólica exata. A abordagem divide-se em duas etapas principais:

• Etapa 1: Certificação Computacional Global (Otimização)

  • Modelo de Otimização: Os autores formulam o problema como um modelo MINLP. Para lidar com a não suavidade da função objetivo (mínimo de áreas absolutas), eles utilizam variáveis auxiliares contínuas para as áreas sinalizadas e variáveis binárias para selecionar o sinal, evitando o uso de grandes constantes $M$ (Big-M) que enfraquecem os relaxamentos.
  • Estratégia de Quebra de Simetria: A maior contribuição metodológica é uma estratégia de quebra de simetria baseada na estrutura de fronteira das configurações ótimas.
    • Eles provam teoricamente que, para $n \ge 5$, pelo menos cinco vértices do casco convexo dos pontos devem residir na fronteira do quadrado unitário.
    • Com base nisso, eles fixam a priori as coordenadas de cinco pontos nas bordas (esquerda, inferior, direita, superior) e impõem uma ordem anti-horária e restrições de ordenação nas coordenadas internas.
    • Isso elimina a simetria do grupo diedral ($D_4$) e a simetria de permutação dos pontos ($S_n$), reduzindo drasticamente a árvore de busca.
  • Fixação de Sinais: A estrutura de fronteira permite fixar o sinal (positivo ou negativo) de certas áreas de triângulos antes da resolução, eliminando variáveis binárias desnecessárias.
  • Resultado: O solver Gurobi resolve o modelo para $n=9$ em cerca de 15 minutos em um computador desktop padrão, uma melhoria de mais de uma ordem de magnitude em relação ao esforço de um dia relatado em trabalhos anteriores.

• Etapa 2: Refinamento Analítico Exato (Símbolo)

  • A solução numérica da Etapa 1 identifica quais triângulos são "críticos" (área mínima) e quais pontos estão na fronteira.
  • Essas observações estruturais são usadas para criar um sistema de equações polinomiais exatas (igualando as áreas dos triângulos críticos).
  • O sistema é resolvido usando álgebra computacional (SymPy e bases de Gröbner). Para casos complexos ($n=9$), onde a resolução direta falha, eles utilizam uma abordagem de "numérico para simbólico", identificando o corpo numérico subjacente (ex: $\mathbb{Q}(\sqrt{65})$) a partir das coordenadas numéricas certificadas e refinando a solução.

3. Contribuições Principais

1. Formulação MINLP Mais Forte: A introdução de uma estratégia de quebra de simetria baseada na fronteira e a eliminação de parâmetros Big-M resultaram no modelo mais eficiente já proposto para este problema.
2. Prova de Optimalidade Global para $n=9$: O trabalho fornece a primeira prova rigorosa de que a configuração descoberta por Comellas e Yebra em 2002 para $n=9$ é globalmente ótima.
3. Coordenadas Exatas: O método gera coordenadas exatas (na forma de números algébricos) para todas as configurações ótimas de $n=5$ a $n=9$, confirmando resultados anteriores e, em alguns casos, simplificando a apresentação matemática.
4. Reprodutibilidade: Todos os códigos, dados e configurações foram disponibilizados publicamente, estabelecendo uma base verificável para pesquisas futuras.

4. Resultados Chave

• Desempenho Computacional:
  • $n=5$: 0,13 segundos.
  • $n=6$: 0,7 segundos.
  • $n=7$: 1,75 segundos.
  • $n=8$: 14,03 segundos.
  • $n=9$: 908 segundos (~15 minutos).
  • Comparação: O trabalho anterior de Monji et al. (2025) levou cerca de um dia para $n=9$; o método anterior de Chen et al. (2017) levou 125 dias.
• Coordenadas Exatas Derivadas:
  • Para $n=5$, confirma-se $\Delta_5 = \sqrt{3}/9$.
  • Para $n=6$, confirma-se $\Delta_6 = 1/8$ e revela-se uma família de soluções de um parâmetro.
  • Para $n=7$, a solução envolve a raiz de um polinômio cúbico irreduzível ($19f^3 - 27f^2 + 11f - 1 = 0$).
  • Para $n=8$, a solução envolve $\sqrt{13}$.
  • Para $n=9$, a solução envolve $\sqrt{65}$, com $\Delta_9 = \frac{-11 + 9\sqrt{65}}{320}$.
• Observações Estruturais:
  • O número de triângulos críticos cresce com $n$, mas não de forma estritamente monótona.
  • As áreas dos triângulos não críticos (aqueles maiores que o mínimo) agrupam-se em um pequeno número de valores distintos, sugerindo uma rigidez estrutural oculta nas configurações extremas.

5. Significado e Impacto

Este trabalho representa um marco na interseção entre otimização combinatória e geometria computacional. Ele demonstra que problemas geométricos complexos, anteriormente considerados intratáveis para métodos gerais, podem ser resolvidos com certificação global usando solvers MINLP modernos, desde que a formulação incorpore conhecimento teórico profundo (como a estrutura de fronteira).

A metodologia "Otimizar e Refinar" oferece um novo paradigma para a pesquisa em geometria discreta: usar a computação numérica para guiar a descoberta da estrutura algébrica e, em seguida, usar a álgebra simbólica para provar a optimalidade e obter soluções exatas. Isso abre caminho para a resolução de casos maiores (como $n=10$) e para a investigação de novas conjecturas sobre a distribuição de áreas em conjuntos de pontos extremos.