  $\renewcommand{\Re}{\mathbb{R}}$ We re-examine 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.
  For vertical decomposition, the combinatorial dimension is only $2d$, the
primal shatter dimension is at most $d(d+1)$, and the VC-dimension is at least
$1 + d(d+1)/2$ and at most $O(d^3)$. For bottom-vertex triangulation, both the
primal shatter dimension and the combinatorial dimension are $\Theta(d^2)$, but
there seems to be a significant gap between them, as the combinatorial
dimension is $\frac12d(d+3)$, whereas the primal shatter dimension is at most
$d(d+1)$, and the VC-dimension is between $d(d+1)$ and $5d^2 \log{d}$ (for
$d\ge 9$).
  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. The best query time that we can obtain is $O(d^3\log n)$,
instead of $O(d^4\log d\log n)$ in Meiser's algorithm. For these bounds to
hold, the preprocessing and storage are rather large (super-exponential in
$d$). We discuss the tradeoff between query cost and storage (in both
approaches, the one using bottom-vertex trinagulation and the one using
vertical decomposition).
