One of these parameters is the classical VC-dimension, and its associated primal shatter dimension, of a suitably defined corresponding range space. Another parameter, which we refer to here as the combinatorial dimension, is the maximum number of hyperplanes that are needed to define a cell that can arise in the decomposition of some sample of the input hyperplanes; this parameter arises in Clarkson's (and later Clarkson and Shor's) random sampling technique.
We re-examine these parameters for the two main space decomposition techniques - bottom-vertex triangulation, and vertical decomposition, including their explicit dependence on the dimension $d$, and discover several unexpected phenomena, which show that, in both techniques, there are large gaps between the VC-dimension (and primal shatter dimension), and the combinatorial dimension.
Our main application is to point location in an arrangement of $n$ hyperplanes is $\Re^d$, in which we show that the query cost in Meiser's algorithm can be improved if one uses vertical decomposition instead of bottom-vertex triangulation, at the cost of some increase in the preprocessing cost and storage (which seem to be stated incorrectly, and are not worked out, in Meiser's work). Our improved bounds rely on establishing several new structural properties and improved complexity bounds for vertical decomposition, which are of independent interest, and which we expect to find additional applications.