Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
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
1  
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

2 Answers 2

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$.

share|improve this answer
3  
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
1  
@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
3  
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

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?

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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