On the Combinatorial and Topological Complexity of a Single Cell

The problem of bounding the combinatorial complexity of a single connected component (a single cell) of the complement of a set of n geometric objects in Rk of constant description complexity is an important problem in computational geometry which has attracted much attention over the past decade. It has been conjectured that the combinatorial complexity of a single cell is bounded by a function much closer to O(nk-1) rather than O(nk) which is the bound for the combinatorial complexity of the whole arrangement. Currently, this is known to be true only for k is less than or equal to 3 and only for some special cases in higher dimensions.
A classic result in real algebraic geometry due to Oleinik and Petrovsky, Thom and Milnor, bounds the topological complexity (the sum of the Betti numbers) of basic semi-algebraic sets. However, until now no better bounds were known if we restricted attention to a single connected component of a basic semi-algebraic set.
In this paper, we show how these two problems are related. We prove a new bound on the sum of the Betti numbers on one connected component of a basic semi-algebraic set which is an improvement over the Oleinik-Petrovsky-Thom-Milnor bound. This also implies that the topological complexity of a single cell, measured by the sum of the Betti numbers, is bounded by O(nk-1). The techniques used for proving this topological result combined with those developed by Halperin and Sharir for the single cell problem in three dimensions allow us to prove a bound of O(nk-1+E) on the combinatorial complexity of a single cell.
Finally, we show that under a certain natural geometric assumption on the objects (namely that, whenever intersect the intersection is robustly transversal on average) it is possible to prove a bound of O(nk-1) on the combinatorial complexity of a single cell. We also show that this geometric assumption is satisfied by most arrangements and deduce that the expected complexity of a single cell in a randomly chosen arrangement is O(nk-1).