Discrepancy measures how uniformly distributed a point set is with respect to a given set of ranges. There are two notions of discrepancy, namely continuous discrepancy and combinatorial discrepancy. Depending on the ranges, several possible variants arise, for example star discrepancy, box discrepancy, and discrepancy of half-spaces. In this paper, we investigate the hardness of these problems with respect to the dimension d of the underlying space. All these problems are solvable in time n^O(d) , but such a time dependency quickly becomes intractable for high-dimensional data. Thus it is interesting to ask whether the dependency on d can be moderated. We answer this question negatively by proving that the canonical decision problems are W[1]-hard with respect to the dimension. This is done via a parameterized reduction from the Clique problem. As the parameter stays linear in the input parameter, the results moreover imply that these problems require n^ (d) time, unless 3-Sat can be solved in 2^o(n) time. Further, we derive that testing whether a given set is an -net with respect to half-spaces takes n^ (d) time under the same assumption. As intermediate results, we discover the W[1]-hardness of other well known problems, such as determining the largest empty star inside the unit cube. For this, we show that it is even hard to approximate within a factor of 2^n .
Given two finite sets of points X+ and X− in Rn, the maximum box problem consists of finding an interval (“box”) B e lx : l ≤ x ≤ ur such that B ∩ X− e ∅, and the cardinality of B ∩ X+ is maximized. A simple generalization can be obtained by instead maximizing a weighted sum of the elements of B ∩ X+. While polynomial for any fixed n, the maximum box problem is NP -hard in general. We construct an efficient branch-and-bound algorithm for this problem and apply it to a standard problem in data analysis. We test this method on nine data sets, seven of which are drawn from the UCI standard machine learning repository. We study the question of finding a deepest point in an arrangement of regions and provide a fast algorithm for this problem using random sampling, showing it sufficient to solve this problem when the deepest point is shallow. This implies, among other results, a fast algorithm for approximately solving linear programming problems with violations. We also use this technique to approximate the disk covering the largest number of red points, while avoiding all the blue points, given two such sets in the plane. Using similar techniques implies that approximate range counting queries have roughly the same time and space complexity as emptiness range queries. Given a set of blue points and a set of red points in ddimensional space, we show how to find an axis-aligned hyperrectangle that contains no red points and as many blue points as possible. Our algorithm enumerates the set of relevant hyperrectangles (inclusion maximal axisaligned hyperrectangles that do not contain a red point) and counts the number of blue points in each one. The runtime of our algorithm depends on the total number of relevant hyperrectangles. We prove asymptotically tight bounds on this quantity in the worst case. The techniques developed directly apply to the maximum empty rectangle problem in high dimensions.