On the combinatorial and topological complexity of a single cell

The problem of bounding the combinatorial complexity afa single connected component (a single cell) of the complement of a set of n geometric objects in R-k, each object 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(n(k-1)) rather than O(n(k)) which is the bound for the combinatorial complexity of the whole arrangement. Till now, this was known to be true only for k less than or equal to 3 and only for same special cases in higher dimensions. A classic result in real algebraic geometry due to Oleinik-Petrovsky, Thom and Milnor, bounds the topological complexity (the sum of the Betti numbers) of basic semi-algebraic sets. However; till 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 of 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(n(k-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(n(k-1+epsilon)) on the combinatorial complexity of a single cell. Finally, we show that under a certain natural geometric assumption on the objects (namely that, whenever they intersect the intersection is robustly transversal on average) it is possible to prove a bound of O(n(k-1)) on the combinatorial complexity of a single cell.