Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
share
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 Θ(d^2), but there seems to be a significant gap between them, as the combinatorial dimension is 1/2d(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 d (for d> 9). Our main application is to point location in an arrangement of n hyperplanes is ^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 n), instead of O(d^4 d 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).
READ FULL TEXT