The Combinatorial and Topological Complexity of a Single Cell

Abstract. 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 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. Until now, this was known to be true only for k ≤ 3 and only for some special cases in higher dimensions.

A classic result in real algebraic geometry due to Oleinik and Petrovsky [15], Thom [18], and Milnor [14], 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 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+ε ) 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) it is possible to prove a bound of O(n ^k-1 ) on the combinatorial complexity of a single cell.

Authors and Affiliations

1. School of Mathematics and College of Computing, Georgia Institute of Technology, Atlanta, GA 30332, USA saugata@math.gatech.edu, , , , , , US

   Saugata Basu

Reprints and permissions