Comment by tejstead
6 hours ago
> 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?
I wonder if there are some other related problems for small-n cases that I could add somewhere on this website?
Maybe here are the easiest ones to state:
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.
[1] https://arxiv.org/pdf/2607.20422