Sharp estimates on random hyperplane tessellations

Abstract

We study the problem of generating a hyperplane tessellation of an arbitrary set $T$ in ${\mathbb{R}}^n$, ensuring that the Euclidean distance between any two points corresponds to the fraction of hyperplanes separating them up to a pre-specified error $\delta$. We focus on random gaussian tessellations with uniformly distributed shifts and derive sharp bounds on the number of hyperplanes $m$ that are required. Surprisingly, our lower estimates falsify the conjecture that $m\sim {\ell }_{\ast }^2(T)/{\delta }^2$, where ${\ell }_{\ast }^2(T)$ is the gaussian width of $T$, is optimal.