Error Resilient Space Partitioning

Abstract A major research area in discrete geometry is to consider the best way to partition the d -dimensional Euclidean space $$\mathbb {R}^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> </mml:math> under various quality criteria. In this paper we introduce a new type of space partitioning that is motivated by the problem of rounding noisy measurements from the continuous space $$\mathbb {R}^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> </mml:math> to a discrete subset of representative values. Specifically, we study partitions of $$\mathbb {R}^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> </mml:math> into bounded-size tiles colored by one of k colors, such that tiles of the same color have a distance of at least t from each other. Such tilings allow for error-resilient rounding, as two points of the same color and distance less than t from each other are guaranteed to belong to the same tile, and thus, to be rounded to the same point. The main problem we study in this paper is characterizing the achievable tradeoffs between the number of colors k and the distance t , for various dimensions d . On the qualitative side, we show that in $$\mathbb {R}^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> </mml:math> , using $$k=d+1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:mi>d</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> colors is both sufficient and necessary to achieve $$t&gt;0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> . On the quantitative side, we achieve numerous upper and lower bounds on t as a function of k . In particular, for $$d=3,4,8,24$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>=</mml:mo> <mml:mn>3</mml:mn> <mml:mo>,</mml:mo> <mml:mn>4</mml:mn> <mml:mo>,</mml:mo> <mml:mn>8</mml:mn> <mml:mo>,</mml:mo> <mml:mn>24</mml:mn> </mml:mrow> </mml:math> , we obtain sharp asymptotic bounds on t , as $$k \rightarrow \infty $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>→</mml:mo> <mml:mi>∞</mml:mi> </mml:mrow> </mml:math> . We obtain our results with a variety of techniques including isoperimetric inequalities, the Brunn-Minkowski theorem, sphere packing bounds, Bapat’s connector-free lemma, and Čech cohomology.