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

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.