Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The following theorem is from Aronov, Naiman, Pach and Sharir's An invariant property of balls in arrangements of hyperplanes. I would like to state them and then ask if any related problem/theorem is known since the paper was released in 1993.

Let $H$ be a collection of $n$ hyperplanes in $d$-space in general position. For each tuple of $d+1$ hyperplanes of $H$, consider the open ball inscribed in the simplex that they form. Let $B_{k}$ denote the number of such balls intersected by exactly $k$ hyperplanes, for $k=0,1, \cdots, n-d-1$. Then $$B_{k}=\binom{n-k-1}{d}$$

In the paper, they used a very clever combinatorial proof to show such an invariant property.

Here I am trying to find any connected problem to this. For example, is the case when $d=2$ or $3$ a known theorem?

Also I have thought of the cell decomposition property in incidence geometry, which states

Let $L$ be a finite collection of lines in $R^2$, and let $r \ge 1$. Then it is possible to find a set of $O(r)$ lines in the plane, which subdivide $R^2$into $O(r^2)$ convex regions (or cells), such that the interior of each such cell is incident to at most $O(|L|/r)$ lines.

Is this related?

share|cite|improve this question
I don't understand your first question. You seem to be saying that for general $d$ this is a known theorem, going back to 1993, and then asking whether it's a known theorem for $d=2$ or $3$. – Gerry Myerson Apr 4 '11 at 3:33
@Gerry: Perhaps Thomas meant: Are the special cases $d=$ and $d=3$ previously known theorems, perhaps in another guise? – Joseph O'Rourke Apr 4 '11 at 11:35
@Joseph, perhaps. Thomas? – Gerry Myerson Apr 5 '11 at 0:42
@Gerry, yes I mean if the special cases are previously known. @Joseph, Thanks for the clarification. – Thomas Z Apr 5 '11 at 4:27
I do not think that creating a regular cell decomposition could help, as it only provides a (tight) asymptotic for the number of lines intersecting a cell where here we are looking for a sharp bound, so we cannot even afford one mistake. Of course a very tricky argument could go around this fact but it seems unlikely. Also, there proof is very simple, so I do not know if it could be further simplified for lower dimensions (except that for d=1 the geometric observation is trivial and you do not need induction there). – domotorp Apr 5 '11 at 5:30

Your Answer


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

Browse other questions tagged or ask your own question.