<p>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.</p>
<p>Another natural generalization is to consider hyperplanes instead of lines. Here, you have Beck's &quot;other&quot; theorem:</p>
<blockquote>
<p><strong>Theorem</strong>: For any <span class="math-container">$d \geq 2$</span>, there are constants <span class="math-container">$\beta_d, \gamma_d \in (0,1/2]$</span> such that for any set <span class="math-container">$P$</span> of <span class="math-container">$n$</span> points in <span class="math-container">$\mathbb{R}^d$</span>, at least one of the following holds:</p>
<ul>
<li>a hyperplane contains at least <span class="math-container">$\beta_d n$</span> points of <span class="math-container">$P$</span></li>
<li>the <span class="math-container">$d$</span>-tuples of <span class="math-container">$P$</span> span at least <span class="math-container">$\gamma_d n^d$</span> distinct hyperplanes.</li>
</ul>
</blockquote>
<p>Here, a hyperplane is a <span class="math-container">$(d-1)$</span>-dimensional flat. For <span class="math-container">$d=2$</span>, this is essentially what you stated. The restriction that <span class="math-container">$\beta_d \leq 1/2$</span> is from the example of having two skew lines in <span class="math-container">$\mathbb{R}^3$</span> containing <span class="math-container">$n/2$</span> points each, where the number of spanned planes is <span class="math-container">$n$</span>. For more, see: <a href="http://www.cs.elte.hu/%7Eelekes/Abstracts/elest.ps" rel="noreferrer">http://www.cs.elte.hu/~elekes/Abstracts/elest.ps</a></p>

CC BY-SA 3.0
2014-12-24T11:50:17.360Z
2014-12-24T11:50:17.360Z
2020-06-17T09:38:08.363Z
arnab
<p><strong><a href="http://en.wikipedia.org/wiki/Beck&#39;s_theorem" rel="nofollow">Beck's theorem</a></strong> 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. </p>

<p>Formally, the statement of the theorem is as follows:</p>

<p><strong>Theorem:</strong> 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 &lt; n-2$, then there exist $\Omega(nk)$ lines determined by the points of $S$.</p>

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

CC BY-SA 3.0
2014-12-24T12:23:36.360Z
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.
Saeed
<co.combinatorics><computational-geometry>
Generalization of Beck's theorem
Ram
# Generalization of Beck's theorem

(Asked by: username_0 on 2014-12-24)

**[Beck's theorem](http://en.wikipedia.org/wiki/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)$?

**Tags:** co.combinatorics, computational-geometry
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2014-12-24. Score: 5 | Accepted answer

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](http://www.cs.elte.hu/%7Eelekes/Abstracts/elest.ps)


---

