Heilbronn Triangle Problem

In mathematics, the Heilbronn triangle problem is a typical question in the area of irregularities of distribution, within elementary geometry.

Consider region D in the plane: a unit circle or general polygon — the asymptotics of the problem, which are the interesting aspect, aren't dependent on the exact shape. Place a number n of distinct points (greater than three) within D: every 3 out of n points define a triangle. For a given arrangement of the n points we are interested in the area of smallest triangle. Over all possible arrangements we want to maximize the area of this smallest triangle. The Heilbronn triangle problem involves therefore the extremal case: the maximum of the area of the smallest triangle over all arrangements. The question was posed by Hans Heilbronn, of giving an expression of this quantity, denoted by Δ(n). This is therefore formally of the shape

Δ(n) = max_{X in C(D,n)} min_{triangles T of X} Area of T.

The notation here says that X is a configuration of n points in D, and T is a triangle with three points of X as vertices.

Heilbronn initially conjectured in the early 50s that this area would be of order

Δ(n) ~ ·n−2;

Erdos showed also in the 50s that this conjecture is true provided n is prime.

But it is now known that Hielbronn's conjecture is false since

A·n−2log n ≤ Δ(n) ≤ B·n−8/7exp(C√log n)

where A, B and C are constants.

There have been many variations of this problem including the expected case of a uniformly random arrangement here denoted by R(n) which is of order

R(n) ~ ·n−3.