MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Does a positive real number $k\geq1$ exist such that for every finite set $P$ of points in the plane (with the property that no three points of $P$ lie on a common line and $|P|\geq3$), one can choose a subset $Q$ of $P$ with $|Q| \geq |P|/k$ points and with the property that there exist two different points $a$ and $b$ in $Q$ such that no line $\overline{(p,q)}$ through two different points $p,q$ of $Q\backslash\{a,b\}$ crosses the interior of the segment $(a,b)$?

If such a number exists, what is the smallest integer $k$, fulfilling the property?

If you take a set $P=\{a,b,c\}$ with three points, then you can set $P=Q$ since no line crosses the interior of the segment $(a,b)$. However, a counterexample for $k=1$ is given below by Reid Barton.

share|cite|improve this question
What is Q{a,b}? – JSE Oct 17 '09 at 19:34
I was not able to typeset Q \ {a,b}, sorry. – Florian Oct 18 '09 at 10:21

I would bet that the answer to this question is that such k does not exist. In order to construct a contrexample to any k I would consider a very large square of the size Nk x Nk, N>>1 and take all the integer points inside of it. Now perturb just a litte bit all these (Nk)^2 points in such a way, that no 3 lay on one line. It looks that this configuration will be contrexample for large N. The reason to think like this is that before we perterb this configuartion for every segment ab there is approximatively at least approximatively (Nk)^3 pairs of points inside of the square such that the line throw them intersect given segment. It seems that you have to throw too many points.

share|cite|improve this answer
Also there is Pick's theorem in this case if there are Nk^2 points then the diameter must be Nk and any two points must be separted by 1 and if we get a triangle with a third Nk away orthogonal to the two points the area of the triangle must be Nk/2 and there must be Nk/2 points inside or Nk on the diameter that does not take into account pertubation but this looks like it might produce a counterexample. – Kristal Cantwell Nov 4 '09 at 5:08

Still not an answer, but I like this question and thought I'd say a little more:

Write N for |P| and consider m(P), the infimum, over all {a,b} in P, of the number of lines which join two elements of P and which cross the segment ab. I think what you want is equivalent to an upper bound on this infimum. (Reid's examples shows that it need not be 0, at any rate.) You are asking wheter m(P) < cN for some c < 1; I wonder whether it might not actually be o(N).

I tried to imagine how I would solve this problem if I were good at harmonic analysis and this is the thought I had. If m(P) is large, then a lot of lines through pairs of points in P "nearly intersect" where they cross a short line segment {a,b}. So the union of all these lines have more "focuses" than you might expect. Shrink P so that it fits in a unit disc. Let delta be some small real number to be optimized later. For each pair x,y from P, let f_{x,y}, a function on the disc, be the characteristic function of the set of points which are within delta of the line xy but not within delta of x or y -- a "twice-punctured thin rectangle." Then let f be the sum of f(x,y) over all pairs x and y.

I would think that if m(P) is large, then f would be surprisingly big in the vicinity of any short line segment in P. And I guess the hope would be that you could bound |f|_p above in some other way so as to derive a contradiction.

Update: The above now seems kind of BSy to me, if anyone's still reading this. In particular I think o(N) seems too much to ask for. I'd like to know what the answer is for N = n^2 lattice points arranged in a square.

share|cite|improve this answer

I have started with the perturbed lattice suggested in Dmitri's answer and using it I think I can show such a $k$ cannot exist. If it does fix $k$. We choose $n$ very large we take $n$ times $n$ grid of points in a square grid since we cannot have three points in a line we perturb each amount by a small quantity small enough not to cause any point within a triangle of other points in the grid to be outside the triangle or on the boundary in the new grid. The rest of this proof will be about points on a lattice when we reach a certain point we will use the above to get a contradiction in the perturbed set of points.

For any pair of points $A$ and $B$ the number of points whose distance from the line containing the points is less than $nk^{2}$ is less than $\sqrt2n^{2}k^{2}$ (we bound the number of points by the number of points whose distance from the line segment with greatest length which is that connecting two diagonal points. This line segment has length $\sqrt2n$ multiplying by the distance gives $\sqrt2n^{2}k^{2}$. So we have $n^2k-\sqrt2n^{2}k^{2}$ points whose distance from the line containing the two points is greater than $nk^{2}$. Now I can use Pick's theorem to show that there must be at least $nk^{2}/2$ points in the triangle or twice as many on the border of the triangle. I use the distance of the point to the line containing the line segment as the altitude an assume the line segment has at least length one to get a lower bound on the area of the triangle.

Now if any of these points are inside the triangle then the line connecting this point and the point of the triangle not equal to the two points of the segment must pass through the line segment but we cannot have this. If any of the lattice points lie on the line segment AB then the area will increase by an amount greater than one for each point and there will be more points that have to lie on the other two sides or the interior. So we can ignore these points in our argument

Now I choose $n$ large enough so that $n^{2}k-\sqrt2n^{2}k^{2}/16$ satisfies the following property the number of integers whose prime factor are all less than $k^{-100}$ is less than $(n^{2}k-\sqrt2n^{2}k^{2})k^{100}/16$. I can do this because for any set of primes the percentage of numbers divided by members of those primes only goes to zero as n goes to infinity.

So we have $n^{2}k-\sqrt2n^{2}k^{2}$ points whose distance from the line containing the two points is greater than $nk^{2}$ we divide them into 16 sets depending on whether their $x$ and coordinates are greater than the $x$ and $y$ coordinates of the two points. So we will have one set of $n^{2}k-\sqrt2n^{2}k^{2}/16$ points whose relation with the coordinates of $x$ and $y$ is always the same we can use the above property of $n$ to get the the number of points whose greatest prime factor in the distance $y$ from the first point is greater than $k^{-100}$ and whose greatest prime factor in the difference from the $y$ coordinate of the second point is greater than $k^{-100}$. To see this note that the number of points which don't satisfy this property with respect to the first coordinate is $(n^{2}k-n^{2}k^{102}/16$ and the number of points which don't satisfy this property with respect to the second coordinate is $1/16(n^{2}k-\sqrt2n^{2}k^{102}$ assuming the worst case that the sets are disjoint and subtracting from $n^{2}k-\sqrt2n^{2}k^{2}/16$ we get $n^{2}k-\sqrt2n^{2}k^{2}/16-(n^{2}k-\sqrt2n^{2}k^{102}$.Then we do the same with the $x$ coordinate ending up with $1/16(n^{2}k-n^{2}k^{2}-2\sqrt2n^{2}k^{102})$.

We want to limit the number of points on the the line $PA$ by getting a large prime to divide the different of the $x$ coordinates of the two points or the difference of the $y$ coordinates of the two points and also the same for $PB$. However for this to work the large prime cannot divide both coordinates.

So we have to filter out all points $P$ where the difference of the $x$ coordinate of $P$ from the $x$ coordinate of $A$ is divisible by a prime $q$ greater than $k^{-100}$ and the difference of the $y$ coordinate of $P$ from the $y$ coordinate of $A$ is divisible by the same prime $q$. Fortunately we can bound this by $n^{2}$ multiplied by the series $1/x^{2}$ with $x$ greater than $k^{-100}$ which sums to roughly $k^{100}$ and $2(k^{100})n^{2}$ is much less than $1/16(n^{2}k-n^{2}k^{2}-2\sqrt2n^{2}k^{102})$ and an error term.

The error term can be viewed as extra points near the edge of the grid of points whose $x$ coordinate and $y$ coordinate differ from the $x$ coordinate and $y$ coordinate of $A$ by a multiple of $q$. The point is that some of the points near the edge of the square may not be counted. These can be bounded by the set of points whose $x$ and $y$ coordinates differ from $A$(or $B$, we are doing this for both points) by a multiple of $q$ and one of those differences is the largest multiple of $q$ at which such a difference occurs. Thus these points lie on the edges of a square we bound the error as follows for a certain value of $n/q$ this square will have less points on it than inside so we just add another copy of the series and that takes care of them. Other wise we have $n/q$ is small and the ratios of the multiples of $q$ are limited and we can cover them by taking all the grid points that lie on a certain set of lines.

For $q$ such that $n/q$ is greater than 10 the error will be less than the series as the points at the edge of the square will bound the error. So for both $x$ and $y$ we take an additional copy of the original series.If we have $n/q$ less than 10 than the error will be bound by the border of the square and the points on the border of the square will have certain ratios as $n/q$ is less than 10 the ratio two numbers less then 10 so we can remove in addition all lines through $A$(and $B$ we have to do this for each point)whose slope is a ratio of two numbers less than 10. There will be less than a 100 such lines so we will subtract at most $100n$. This will still leave the remaining number of points greater than zero as for large $n$ $100n$ will be much less than a quadratic function of $n$ and $2(k^{100})n^{2}$ is much less than $1/16(n^{2}k-n^{2}k^{2}-2\sqrt2n^{2}k^{102})$ as mentioned above.

So we have at least one point $P$ whose distance from the line containing $A$ and $B$ is greater than $nk^{2}$ satisfying the above properties and hence the distance from the two points is greater than this amount for each of the two points in particular there must be one coordinate of each point whose distance is $1/\sqrt2$ this amount that difference coordinate of these coordinates distance from $P$ must be divisible by a large prime greater than $k^{-100}$ and the other coordinate is not. but that limits the points on the line segments from $P$ to $A$ and $B$ to the distance times $k^{100}$ for the other point we get a similar limitation but by Pick's theorem we need at least $2n^{2}k^{2}$ points on the edges of the triangle to prevent points from forming in the interior and giving a contradiction. The factor of $k^{100}$ prevents this and forces a point in the interior which remains in the interior of the perturbed points and thus the line from this point and $P$ will cross the line segment between $A$ and $B$ forcing a contradiction.

share|cite|improve this answer
I have added material to take care of one case. – Kristal Cantwell Nov 28 '09 at 17:10

I'm very curious where this problem comes from, since it is related to some stuff I've been thinking about.

The smallest counterexample for k=1 seems to be the set of six points containing the vertices of a regular pentagon plus its center. Alas, I don't know how to say anything about this problem for k > 1.

share|cite|improve this answer
I think that your counterexample of six points for one is also a counterexample for any k less than 6/5 and greater than one. – Kristal Cantwell Nov 4 '09 at 4:59

It's not the same thing, but for every two points a and b in P there exists a subset Q of P with |Q| = Ω(√|P|) so that either no line(p,q) through two points of Q crosses segment(a,b), or every line(p,q) crosses the segment.

To see this, first observe that by deleting at most half the points we may assume that segment(a,b) is an edge of the convex hull of P. Once this is true, Q has the desired property if and only if the radial sorted order of Q around point a is the same as (or the reverse of) the radial sorted order around point b. Therefore, the result follows immediately from the Erdős–Szekeres theorem. The case where the two sorted orders are the same is the one where no line passes through the segment; the case where the order is reversed is the one where every line passes through the segment.

share|cite|improve this answer

Very interesting question. I don't have an answer, only a remark that the property you ask Q to have only depends on the so-called "order type" of Q, a combinatorial invariant which keeps track of which triples of points {a,b,c} in Q have the property that c is to the left of the directed line from a to b. The number of order types on a set of size n is on order (n!)^4, as discussed here at my blog (in the comments.) I wonder how many of these contain a pair of points which lie on the same side of the line through any other two points?

share|cite|improve this answer

(Would comment if I could.)

The recursion is off in airplanepeanuts' argument, as far as I can tell.

Let me not call Reid's configuration P (that name is used in the question) but, say, a sexunx, and let me just discuss the |P|=6^2 case for simplicity. The problem is that we don't necessarily have to remove all 6 points of one small sexunx, because we might instead choose a and b to lie inside the same small sexunx S; then no lines between points in two different small sexunxes S', S'' \neq S cross (a,b). If you pick (a,b) that way, the troublesome cases are actually lines between one point in S and one point not in S.

share|cite|improve this answer

i was wrong. sorry.

share|cite|improve this answer

Your Answer


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.