Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location (Q2189742)

Let \(H\) be a set of \(n\) hyperplanes in \(\mathbb{R}^{d}\) and let \(\mathcal{A}(H)\) denote the arrangement of \(H\). The paper is devoted to the point-location problem in \(\mathcal{A}(H)\) which boils down to preprocess \(H\) into a data structure that support efficient point-location queries, each of which specifies a point \(q \in \mathbb{R}^{d}\) and asks for the cell of \(\mathcal{A}(H)\) that contains \(q\). One can represent the output cell \(C\) by its sign pattern with respect to hyperplanes \(H\), where the sign of \(C\) with respect to a hyperplane \(h \in H\) is \(0\) if \(h\) contains \(C\), \(+1\) if \(C\) is on the positive side of \(h\), and \(-1\) otherwise. In the present paper, the authors provide a careful analysis of Meiser's work which leads to improved bounds for point locations and to understand better the theory behind the mentioned work centered around the random sampling and the space decomposition. A standard approach to the point location problem is via random sampling in which one draws a random sample \(R\) of the set \(H\) of given hyperplanes, constructs a suitable decomposition of the arrangement \(\mathcal{A}(R)\) of \(R\), and recurses within each cell \(\tau\) of the decomposition with the so-called conflict list \(K(\tau)\), which is the set of the hyperplanes of \(H\) that cross \(\tau\). The effciency of the resulting algorithm requires that the size of each \(K(\tau)\) should be much smaller than \(|H|\). There are two main methodologies behind this problem, the first one the classical \(VC\)-dimension and its associated primal shatter dimension of a suitable defined range space, and another approach is based on the so-called combinatorial dimension -- it is the maximal number of hyperplanes that are needed to define a cell that can arise in the decomposition of any sample of \(H\). The authors re-examine the mentioned parameters for the two main space decomposition techniques, namely the bottom-vertex triangulation and the vertical decomposition, including their explicit dependence on the dimension \(d\). For the vertical decomposition, the combinatorial dimension is \(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 the bottom-vertex triangulation the combinatorial dimension is \(d(d+3)/2\) 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\geq 3\). The main application (and contribution) of the authors towards the point-location problem is that the query cost in Meiser's algorithm can be improved if one uses the vertical decomposition instead of the bottom-vertex triangulation. The improved bounds rely on new bounds on the complexity of the vertical decomposition (i.e. the number of prisms there). It is worth emphasizing that the paper is extremely well and rigorously written, which is a great asset of this item.