Randomly choosing

points from the plane will lead to a set in general position, but this set is unlikely to have any interesting extremal structure. For example, we expect such a set to span many distinct distances, and it is not clear why such a set should span few convex

-gons. Problems such as the ones above ask for point sets that are in general position while also having some kind of structure. I often find it useful to have examples of such point sets as part of my “Discrete Geometry toolkit”. I am familiar with two very different constructions of such sets. This post describes these two constructions. If you are familiar with additional constructions, do let me know!

**Construction 1: Subsets of the integer lattice.** Our first construction involves finding a large subset of an

section of the integer lattice that is in general position. The basic idea for this construction seems to originate from Erdős (for example, see

this paper of Roth), although we will follow a later

variant of Thiele.

For a prime

, we consider the point set

Note that

is a set of

points from a

section of the integer lattice. We will now show that

does not contain three collinear points or four cocircular points.

* An example of the first construction, created by Gábor Damásdi.*
Three points

and

are collinear if and only if

It is not difficult to check that for three points

, we get

For distinct integers

, this determinant is clearly nonzero. When we also have that

, this determinant is also not a multiple of the prime

. Thus,

We conclude that no three points of

are collinear. We can use a similar argument for the case of cocircular points. Four points

and

are cocircular if and only if

(One can think of this test is as lifting the four points to the paraboloid defined by

in

, and checking if the four lifted points are coplanar. It is known that the intersections of the paraboloid with planes are exactly the lifting of circles to the paraboloid.)

Taking the points

, we get

Since

, we have that

is not a multiple of

. Assuming that the four integers are distinct, none of the elements of the product is a multiple of

. Repeating the above argument, we get that no four points of

are cocircular.

**Construction 2: Projection from a hypersphere.** In our first construction, the point set has some structure since it is a subset of a

section of the integer lattice. The structure in our second construction also originates from a lattice, although in a very different way. This construction comes from a paper of

Erdős, Füredi, Pach, and Ruzsa, and seems to be influenced by earlier ideas of

Behrend.

For a positive integer

, consider the section of the

-dimensional integer lattice

We claim that there exists a hypersphere around the origin that contains many points of

. First, note that

. We also note that the distance between a point

and the origin is

. Every such distance is the square root of an integer between zero and

. That is, the points of

determine at most

distinct distances from the origin. By the pigeonhole principle, there exists a distance

such that at least

points are at distance

from the origin. In other words, the hypersphere

centered at the origin and of radius

contains at least

points of

. Let

be a set of exactly

of these points. To recap,

is a set of

points with integer coordinates on the hypersphere

.

Let

be a generic two-dimensional plane in

(or, if you prefer, a random plane). Let

be the set of points that are projections of the points of

on

. It is not difficult to verify that, on a generic plane, no two points of

are projected to the same point. Similarly, when projecting four points on a generic plane, we do not expect the projections to be cocircular. That is, we may assume that

consists of

distinct points, no four which are cocircular.

It is not true that the projections of any three points on a generic plane are not collinear. If three points are collinear in

, then their projections on

*every* plane would remain collinear. This is why we take the points of

to be on the hypersphere

: Since every line intersects the hypersphere in at most two points, no three points of

are collinear.

Now that we constructed a set

of

points in general position, it remains to see what structure

has. For this purpose, we return to the lattice

in

. It is not difficult to verify that the set of vectors determined by pairs of points of

is

That is, the number of distinct vectors determined by pairs of points of

is

. Since

, the number of distinct vectors determined by pairs of points of

is also

. Let

satisfy

, and let

be a projection from

to a two-dimensional plane. Then

. This implies that the number of distinct vectors determined by pairs of points of

is also

.

From the definition

we obtain

, which in turn implies

. Thus, the number of distinct vectors determined by pairs of points of

is

. (If you are not used to such expressions, note that for every

we have

.) This property shows that

has a strong structure. For example, it immediately implies that the number of distinct distances determined by

is

(and similarly for the number of distinct directions). That is, a set in general position can still determine a relatively small number of distinct distances.