Name
Abstract | ||
|---|---|---|
Consider a geometric range space $(X,c{A})$ 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,c{A})$ on the sum of values in that range e.g., $r_A = sum_{x A} r(x)$ and $b_A = sum_{x A} b(x)$. The $Phi$-maximum range is $A^* = arg max_{A (X,c{A})} Phi(A)$. Our goal is to find some $hat{A}$ such that $|Phi(hat{A}) - Phi(A^*)| leq 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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.4230/LIPIcs.ISAAC.2018.32 | ISAAC |
DocType | Volume | Citations |
Conference | abs/1804.11287 | 1 |
PageRank | References | Authors |
0.43 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Matheny | 1 | 2 | 1.80 |
| Jeff M. Phillips | 2 | 536 | 49.83 |