# Sets of evenly distributed points in the Euclidean plane

Is there a set $P \subset \mathbb{R}^2$ of points in the Euclidean plane whose intersection with every convex subset of $\mathbb{R}^2$ of area $1$ is nonempty but finite?

If the answer is yes, can $P$ be chosen in such way that there is a constant $C_P$ with the property that for every convex subset $S \subset \mathbb{R}^2$ of area $1$ we have $1 \leq |S \cap P| \leq C_P$? -- And if yes, which $P$ admit the smallest $C_P$?

Remarks:

1. Lattices are not examples as there is always an $\epsilon > 0$ such that there are $\epsilon \times \frac{1}{\epsilon}$ rectangles which do not contain a lattice point.

2. The question looks in some sense natural to me, and I wonder whether it has already been considered before. Maybe someone knows a reference?

• The example with the $\epsilon \times \frac{1}{\epsilon}$ rectangles shows that the projections of the set $P$ must be dense on the real line. – Stephen Sturgeon Aug 29 '13 at 17:14
• It seems like you could use a lattice $L$ union a refinement of $L$ minus points inside some ball of radius r. Then keep adding refinements as you get further away from the origin. – Stephen Sturgeon Aug 29 '13 at 17:21

There is a set $P$. For the construction of this set first take the squares of area $1$ whose edges are integers and numerate them. For each square, say $S_n$, you can take a square lattice in it such that any convex inside the square that do not intersect the lattice has area less than $a_n$ for any $a_n>0$, just take a lattice with a very small distance.

Now choose lattices and the $a_n$'s so that $\sum_{n=1}^\infty a_n<1$.

This works because if you have a convex $C$ in $\mathbb R^2$ then $C\cap S_n$ is convex, and if it do not intersect the set $P$ then $$m(C)=\sum_{n=1}^\infty m(C\cap S_n)\leq\sum_{n=1}^\infty a_n<1,$$ where $m(A)$ denotes the area of $A$.

For the second question there is a proof here http://www.math.tau.ac.il/~barakw/papers/dynamical_gowers.pdf that there could not be any constant.

• A convex set of area 1 must be bounded, right? And a bounded set intersects only finitley many unit squares, and each unit square contains only finitely many points of $P$, so I think this does answer the first question (though not the one about $C_P$). – Gerry Myerson Aug 29 '13 at 23:40
• I guess I implied that was clear. – Gerardo Arizmendi Aug 30 '13 at 4:26
• @GerryMyerson: Yes, you are right. -- Gerardo Arizmendi has answered the first question. -- Sorry for my initial misreading! – Stefan Kohl Aug 30 '13 at 9:11
• I think you could explain what you mean by "squares of area 1 whose edges are integers" - I would write instead the unitsquares of the grid. – domotorp Sep 6 '13 at 12:58
• I think I have answered both questions. – Gerardo Arizmendi Apr 3 '18 at 4:33

Your second problem is almost the same as the following old, open problem of Danzer and Rogers: "What is the area of the largest convex region not containing in its interior any one of $n$ given points in a unit square?" Here the big question is whether the answer is $\Theta(\frac 1n)$ or not.

If the answer to the DR-problem is $\omega(\frac 1n)$, then there can be no bound in your problem for the number of points a unit convex set might contain. To see this, suppose by contradiction that you have a $P$ with some $C_P$ bound. Take a $\sqrt n \times \sqrt n$ size square, this contains $\Theta(n)$ points of $P$, to simplify calculations I suppose it contains exactly $n$. By scaling, the DR-problem gives us an empty convex set of size $\omega(1)$, which becomes bigger than $1$ if $n$ is big enough.

In the other direction, I am not sure if the implication holds, so I think your question is an excellent research topic. Can we prove that the two problems are equivalent?

• Interesting! -- Though according to Pach and Tardos (renyi.hu/~tardos/kvazi.pdf), the Danzer-Rogers problem is about rectangles rather than general convex regions. – Stefan Kohl Sep 7 '13 at 16:47
• I have copied the quote from that paper... Anyhow, the problem is the same for rectangles, as any planar convex set has a rectangle whose area is a constant fraction of the whole area. – domotorp Sep 7 '13 at 19:12
• Ah, I see -- the abstract states the problem for rectangles, whereas the introduction does so for convex regions ... -- though, as you say, that is equivalent. – Stefan Kohl Sep 7 '13 at 19:31