Most dispersed set of points in a disk?

Question

Put $1$ billion points in a disk of radius $1$. Consider the minimal area $A$ of a triangle formed by any $3$ points. Where do you put the points so that $A$ is maximal and how much is $A$? Consider the same problem with $N$ points in a domain $\Omega$. How does the maximal value of $A$ behave in the limit $N\to \infty$?

Answer 1

This is the "Heilbronn triangle problem". See Wikipedia for an entry into the literature.

Answer 2

Maybe not an exact answer, but some thoughts to get a foot in the door:

• no three points must be collinear, because otherwise a triangle with area $0$ would exist and thus every set of points in general position would give a better solution.

• if we interpret the task of distributing $n$ points as optimally selecting $n$ points from a larger set of candidate points, then, together with requirement of being general position, this may lead to the idea of taking as the candidate set, from which the $n$ points are selected, the intersection points of a set of carefully chosen lines.

• under the assumption, that our candidate set of points resembles the intersections of set of lines, we have a first condition to be met: namely that no more than two of the selected $n$ points be on the same line.
  That condition has the scent of an assignment problem and, if the lines are also in general position, every intersection point belongs to exactly two lines, making the LP formulation totally unimodular, which in turn means, that the LP solution is integral.

• under the assumption, that a set of candidate points has been selected as described above, we can now turn to estimating the lower bound on the triangle areas;
  a naive, but useful observation is, that it depends on the distance of two points on the same line and on the shortest distance of a point to any other line.

• the next heuristic idea is to put our hopes on the grid-points of a regular grid, that maximises the minimal distance between points on the same grid-line and between parallel grid lines.

• The choice between triangular and quadratic grid can be decided in following way: find the smallest circle, that contains a billion grid points, divide the area of the triangular cell or of a quadratic cell by the squared radius of the containing circle and, chose the one that yields the bigger value.
  At this point we have maximized a lower bound on the smallest triangle area but, there may still be ambiguities about the choice of selecting $n$ of the grid points.

• improving the lower bound: if we have made our choice of grid, we can assume that every grid-line contains at least one of the $n$ selected points and thus, that the minimal triangle-are solely depends on the smallest distance of a pair of selected points on the same grid-line.
  There may be a way to encode the distance between two points on the same grid-line via linear conditions and also have a first idea of how to do it, but I have not yet checked its correctness; maybe I will provide more information in a later edit.

Sorry for the coarse description of the ideas, but maybe they can serve as source of inspiration for others.

Answer 3

A more practical heuristic for generating dispersed point sets inside a compact region $\Omega$, that also generates to higher dimensions is the following, which I would like to call the stay away from the lines heuristic:

Let $V$ denote the set of already determined points and, $L= \{v_i+\lambda(v_j-v_i))| v_i,v_j\in V\wedge i \lt j \}$ the set of lines through the pairs of determined points,
then the next point to be included into $V$ is the element an element of $\Omega$ that maximizes the minimal distance to the lines in $L$.
After the new point has been determined, $L$ has to be updated accordingly.

In case of a disk, one could either start with two antipodal points on the boundary or, with the three equidistant points on the boundary; I am not sure, which of the options will yield the better point set.