Abstract
Consider the geometric range space (X, H_d) where X ⊂ ℝ^d and H_d is the set of ranges defined by ddimensional halfspaces. In this setting we consider that X is the disjoint union of a red and blue set. For each halfspace h ∈ H_d define a function Φ(h) that measures the "difference" between the fraction of red and fraction of blue points which fall in the range h. In this context the maximum discrepancy problem is to find the h^* = arg max_{h ∈ (X, H_d)} Φ(h). We aim to instead find an ĥ such that Φ(h^*)  Φ(ĥ) ≤ ε. This is the central problem in linear classification for machine learning, in spatial scan statistics for spatial anomaly detection, and shows up in many other areas. We provide a solution for this problem in O(X + (1/ε^d) log⁴ (1/ε)) time, for constant d, which improves polynomially over the previous best solutions. For d = 2 we show that this is nearly tight through conditional lower bounds. For different classes of Φ we can either provide a Ω(X^{3/2  o(1)}) time lower bound for the exact solution with a reduction to APSP, or an Ω(X + 1/ε^{2o(1)}) lower bound for the approximate solution with a reduction to 3Sum.
A key technical result is a εapproximate halfspace range counting data structure of size O(1/ε^d) with O(log (1/ε)) query time, which we can build in O(X + (1/ε^d) log⁴ (1/ε)) time.
BibTeX  Entry
@InProceedings{matheny_et_al:LIPIcs.ISAAC.2021.4,
author = {Matheny, Michael and Phillips, Jeff M.},
title = {{Approximate Maximum Halfspace Discrepancy}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {4:14:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772143},
ISSN = {18688969},
year = {2021},
volume = {212},
editor = {Ahn, HeeKap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15437},
URN = {urn:nbn:de:0030drops154377},
doi = {10.4230/LIPIcs.ISAAC.2021.4},
annote = {Keywords: range spaces, halfspaces, scan statistics, finegrained complexity}
}
Keywords: 

range spaces, halfspaces, scan statistics, finegrained complexity 
Collection: 

32nd International Symposium on Algorithms and Computation (ISAAC 2021) 
Issue Date: 

2021 
Date of publication: 

30.11.2021 