The Heilbronn Problem
math.tejstead.com
math.tejstead.com
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...
I wonder if there are some other related problems for small-n cases that I could add somewhere on this website?
1. One can ask the same problem but for k-gons instead of triangles.
2. Given a set of point-line pairs (x1, l1), ..., (xn, ln) [[that is, each xj lies in the line lj]], consider the smallest distance between some xi and lj where i != j. Then as in Heilbronn's problem we want configurations so that this smallest distance is as large as possible.
In 2 here we already see a key feature of 'incidence lower bounds' problems: we need to assume some initial 'trivial incidences' for the problem to make sense at all. If we didn't require them; we could put all the points at the top, and the lines at the bottom, and call it a day! The 'trivial incidences' force the points and lines to be spatially mixed; then we want to find a 'non-trivial incidence'.
Asymptotics for problem 1 are very open (seems decently harder than Heilbronn) but problem 2 was recently solved by Cosmin [1]
Actually, information about (2) immediately gives you something about the Heilbronn problem: take your n points, and use them to define n/2 lines. This gives a family of n/2 points and n/2 lines (forgetting about the 'other' point on each line). Apply the best answer you get to (2), to find a point of distance r to some line. Since that line originally came from two other points, you get a triangle of area ~ r. This is where the best known asymptotics for Heilbronn's problem come from.
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!
Github repo for the site: https://github.com/tejstead/heilbronn-site
Also, check out the entry for square n=16, I added a pretty cool animation there.