14
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 29, 2013 at 17:14
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 29, 2013 at 17:21

2 Answers 2

16
$\begingroup$

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.

$\endgroup$
7
  • 3
    $\begingroup$ 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$). $\endgroup$ Aug 29, 2013 at 23:40
  • 1
    $\begingroup$ @GerryMyerson: Yes, you are right. -- Gerardo Arizmendi has answered the first question. -- Sorry for my initial misreading! $\endgroup$
    – Stefan Kohl
    Aug 30, 2013 at 9:11
  • 3
    $\begingroup$ 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. $\endgroup$
    – domotorp
    Sep 6, 2013 at 12:58
  • 1
    $\begingroup$ I think I have answered both questions. $\endgroup$ Apr 3, 2018 at 4:33
  • 1
    $\begingroup$ Shouldn´t it be accepted? $\endgroup$ Jun 25, 2019 at 18:46
5
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Interesting! -- Though according to Pach and Tardos (renyi.hu/~tardos/kvazi.pdf), the Danzer-Rogers problem is about rectangles rather than general convex regions. $\endgroup$
    – Stefan Kohl
    Sep 7, 2013 at 16:47
  • $\begingroup$ 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. $\endgroup$
    – domotorp
    Sep 7, 2013 at 19:12
  • $\begingroup$ 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. $\endgroup$
    – Stefan Kohl
    Sep 7, 2013 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.