The Heilbronn Problem: New Records Push the Limits of Point Placement
The Heilbronn problem asks how to place n points in a unit-area region so that the smallest triangle formed by any three points is as large as possible. This site tracks the best known configurations for squares, triangles, and optimal convex regions, with exact coordinates, symmetry analysis, and a rational arithmetic verifier. Recent records include a 3.74% gain for the square with n=25 and a 3.46% gain for the convex case with n=31, found with the help of Opus 5.5.
Place n points in a unit-area region such that the smallest triangle determined by any three points achieves the largest possible area, A(n).
- dataflow
What's the criterion for getting listed as the current best known value? (I'm kind of confused why that list isn't infinitely long.)
- arutar
It's cool to see a piece of mathematics that I am personally very interested in show up on HN!
From a pure mathematics standpoint, I am most interested in asymptotics (what happens as n becomes very large).
Some tidbits which might be interesting:
* Here's an argument saying there must always be a triangle of area less than about 1/n. Divide the unit square into n/3 vertical strips. By the pigeonhole principle one of the strips must contain three points. The strip has area about 1/n, so the triangle also has area at most 1/n.
* In contrast, the best known lower bound is something like (log n)/n^2 - very far from 1/n.
* After quite a bit of work by a number of authors, Komlós, Pintz & Szemerédi proved in 1981 an upper bound essentially of the form n^(-8/7), still quite far from the n^2 lower bound!
* Remarkably, there was no progress for over 40 years, until a few years ago two PhD students at MIT (Alex Cohen and Dima Zakharov) along with Cosmin Pohoata beat this upper bound by some small factor, and then later improved it to n^(-7/6) a year or so later. (See [1] for an overview of their work.)
* This problem is related to a more general family of incidence geometry problems called 'lower bounds for incidences': given some collection of geometric objects (say, points and lines), under what conditions can we guarantee that there are in fact more 'almost incidences' than we originally expect?
[1] https://www.quantamagazine.org/the-biggest-smallest-triangle...
- tejstead
Hi there,
I made this website to showcase the Heilbronn problem, which is a classic problem in optimization. Lately there has been a wave of contributions of new records made by amateur mathematicians - you could be one of them!