2018/04/30 by Michael Matheny, Matheny, Michael, Jeff M. Phillips +1 · 2 citations
Computer Science · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.1804.11287
arxiv created 2018/09/27 · arxiv updated 2018/10/01
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 Φ(A) defined on any subset A ∈ (X,cA) on the sum of values in that range e.g., rA = ∑x ∈ A r(x) and bA = ∑x ∈ A b(x). The Φ-maximum range is A^* = arg maxA ∈ (X,cA) Φ(A). Our goal is to find some A such that |Φ(A) - Φ(A^*)| ≤ ε. 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.