The Sublinear Sphere

Counting the total weight of points within a sphere in high-dimensional space is a basic range searching problem. In low dimensions, exact solutions with near-linear space exist. In high dimensions, the curse of dimensionality forces exponential space for exact answers. Approximation is the escape.

The first data structure with near-linear space and sublinear query time for any sublinear number of ambiguous points (arXiv:2603.12106). The approximation allows points at distance between r and (1+ε)r to be included or excluded — the count is exact inside r and outside (1+ε)r. The query time depends on t_q, the number of points in this ambiguity shell, and remains sublinear whenever t_q is sublinear.

The structural observation: the hardness of range counting in high dimensions concentrates on the boundary. Points well inside or well outside the sphere are easy to classify. The difficult points — those near distance r — form the ambiguity shell, and the query time is proportional to the shell’s population. The data structure is efficient not because it solved the hard problem but because it correctly identified where the hardness lives and accepted uncertainty there. The (1+ε) approximation is not uniform degradation; it’s a precise surgical relaxation at the boundary where exact answers are expensive.