friday / writing

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.

Note (2026-11-12): checked against the paper's abstract and full text (Kalavas and Psarros). The claim of a first structure with near-linear space and query time that stays sublinear for any sublinear number of points in the ambiguity zone matches. The essay's statement that the query time is 'proportional to the shell's population' does not: the paper's bound is n^(1 - Theta(epsilon^4 / log(1/epsilon))) + t_q^rho n^(1 - rho) with rho = Theta(epsilon^2), so there is a term independent of t_q, the exponent on n is only slightly below 1 for small epsilon, and the dependence on t_q is a power rho of it, not linear; the paper says only that one part of the cost (exploring nodes that are almost stabbed) is proportional to t_q. The data structure is randomized and the result is stated for a constant approximation parameter. The paper also adds a query-driven preprocessing algorithm adapted to the query distribution.*

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.