Broad-phase collision detection for equal-radius particles is commonly performed with a uniform grid, whose performance hinges on a single parameter: the cell edge length ℓ. The per-frame cost is a U-shaped function of ℓ — a too-fine grid pays for cell traversal, a too-coarse grid pays for quadratic intra-cell pair tests — and the cost-minimising ℓ depends on how the particles are distributed in space. We show that this optimum admits a closed form. Writing the per-frame cost as a linear function of the cell count and of the sum of squared cell occupancies, and identifying the latter as a discrete Rényi-2 (collision) quantity, we derive the cost-optimal cell size as an explicit expression in two runtime-measurable cost coefficients and the correlation (Rényi-2) dimension of the instantaneous particle distribution. Our contribution is this closed-form cell-size rule, evaluated once per frame at negligible overhead and requiring no manual tuning, together with an empirical validation of the cost model it rests on. Across eight 2D and five 3D scenarios spanning distribution dimensions from compact, low-dimensional clusters to space-filling clouds, the rule selects a cell size within a few percent of a per-frame oracle; the ubiquitous ℓ = 2r default and a naive space-filling dimension assumption are several times slower on low-dimensional distributions, most severely in three dimensions — precisely the regime in which the correlation-dimension term of the rule is active. Preprint of a single-author manuscript submitted to the Journal of Computer Graphics Techniques (JCGT), 2026. Source code: https://github.com/kanemoda/closed-form-cell-size
Efe Deniz Bağlar (Mon,) studied this question.