# Practical Low-Dimensional Halfspace Range Space Sampling

arXiv: https://arxiv.org/abs/1804.11307 · HTML: https://mlsanity.com/paper/1804.11307/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2018.

## Built on by (most cited first, 2 of 2)

- [Approximate Maximum Halfspace Discrepancy](https://mlsanity.com/paper/2106.13851/) (2021)
- [Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical](https://mlsanity.com/paper/2209.01147/) (2022)

## Abstract (arXiv)

We develop, analyze, implement, and compare new algorithms for creating varepsilon-samples of range spaces defined by halfspaces which have size sub-quadratic in 1/varepsilon, and have runtime linear in the input size and near-quadratic in 1/varepsilon. The key to our solution is an efficient construction of partition trees. Despite not requiring any techniques developed after the early 1990s, apparently such a result was not ever explicitly described. We demonstrate that our implementations, including new implementations of several variants of partition trees, do indeed run in time linear in the input, appear to run linear in output size, and observe smaller error for the same size sample compared to the ubiquitous random sample (which requires size quadratic in 1/varepsilon). This result has direct applications in speeding up discrepancy evaluation, approximate range counting, and spatial anomaly detection.