balls in arrangements of hyperplanes - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T11:35:35Z http://mathoverflow.net/feeds/question/60518 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/60518/balls-in-arrangements-of-hyperplanes balls in arrangements of hyperplanes Thomas Z 2011-04-04T03:25:29Z 2011-04-04T03:25:29Z <p>The following theorem is from Aronov, Naiman, Pach and Sharir's <a href="http://www.digizeitschriften.de/dms/img/?PPN=GDZPPN000366250" rel="nofollow">An invariant property of balls in arrangements of hyperplanes</a>. I would like to state them and then ask if any related problem/theorem is known since the paper was released in 1993.</p> <blockquote> <p>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}\$\$</p> </blockquote> <p>In the paper, they used a very clever combinatorial proof to show such an invariant property. </p> <p>Here I am trying to find any connected problem to this. For example, is the case when \$d=2\$ or \$3\$ a known theorem? </p> <p>Also I have thought of the cell decomposition property in incidence geometry, which states </p> <blockquote> <p>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.</p> </blockquote> <p>Is this related?</p>