Beck's theorem is a classical result in discrete geometry which describes about the geometry of points in the plane. The result states that a finite collections of points in the plane fall into one of two extremes; one where a large fraction of points lie on a single line, and one where a large number of lines are needed to connect all the points.

Formally, the statement of the theorem is as follows:

Theorem: Let $S$ be a set of $n$ points in the plane. If at most $(n-k)$ points lie on any line for some $0 \leq k < n-2$, then there exist $\Omega(nk)$ lines determined by the points of $S$.

Now, my question is that if the generalization/variation of the above result is known in the case of higher dimension $(dim\geq 3)$?

  • $\begingroup$ Except few sentences all other sentences of the question are exact copy of wiki. Provide a quotation if you copy that amount of text from somewhere else (not from your own). Finally why you didn't see this? "Take for example a set of 2n points in R3 all lying on two skew lines. Assume that these two lines are each incident to n points. Such a configuration of points spans only 2n planes. Thus, a trivial extension to the hypothesis for point sets in Rd is not sufficient to obtain the desired result.", that says generalization first needs a good new definition rather than the trivial ones. $\endgroup$
    – Saeed
    Dec 24 '14 at 12:23

If you are asking if the same statement holds true or not in higher dimensions, it does. Just project all the points to a random 2-dimensional plane.

Another natural generalization is to consider hyperplanes instead of lines. Here, you have Beck's "other" theorem:

Theorem: For any $d \geq 2$, there are constants $\beta_d, \gamma_d \in (0,1/2]$ such that for any set $P$ of $n$ points in $\mathbb{R}^d$, at least one of the following holds:

  • a hyperplane contains at least $\beta_d n$ points of $P$
  • the $d$-tuples of $P$ span at least $\gamma_d n^d$ distinct hyperplanes.

Here, a hyperplane is a $(d-1)$-dimensional flat. For $d=2$, this is essentially what you stated. The restriction that $\beta_d \leq 1/2$ is from the example of having two skew lines in $\mathbb{R}^3$ containing $n/2$ points each, where the number of spanned planes is $n$. For more, see: http://www.cs.elte.hu/~elekes/Abstracts/elest.ps


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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