Block partitions in higher dimensions

Endre Csóka

Published 2023-10-28Version 1

Consider a set $X\subseteq \mathbb{R}^d$ which is 1-dense, namely, it intersects every unit ball. We show that we can get from any point to any other point in $\mathbb{R}^d$ in $n$ steps so that the intermediate points are in $X$, and the discrepancy of the step vectors is at most $2\sqrt{2}$, or formally, $$\sup\limits_{\substack{n\in \mathbb{Z}^+,\ t\in \mathbb{R}^d\\ X\text{ is 1-dense}}}\,\, \inf\limits_{\substack{p_1,\ldots, p_{n-1}\in X\\ p_0=\underline{0},\ p_n=t}}\,\, \max\limits_{0\leq i<j<n} \big\|(p_{i+1}-p_i)-(p_{j+1}-p_j)\big\|\leq 2\sqrt{2}.$$