Computing Approximate Statistical Discrepancy

Consider a geometric range space (X,cA) where each data point x ∈ X has two or more values (say r(x) and b(x)). Also consider a function Phi(A) defined on any subset A ∈ (X,cA) on the sum of values in that range e.g., rA = sumx ∈ A r(x) and bA = sumx ∈ A b(x). The Phi-maximum range is A^* = arg max_A ∈ (X,cA) Phi(A). Our goal is to find some hatA such that |Phi(hatA) - Phi(A^*)| ≤ varepsilon. We develop algorithms for this problem for range spaces with bounded VC-dimension, as well as significant improvements for those defined by balls, halfspaces, and axis-aligned rectangles. This problem has many applications in many areas including discrepancy evaluation, classification, and spatial scan statistics.