  A partition $\mathcal{P}$ of $\mathbb{R}^d$ is called a
$(k,\varepsilon)$-secluded partition if, for every $\vec{p} \in \mathbb{R}^d$,
the ball $\overline{B}_{\infty}(\varepsilon, \vec{p})$ intersects at most $k$
members of $\mathcal{P}$. A goal in designing such secluded partitions is to
minimize $k$ while making $\varepsilon$ as large as possible. This partition
problem has connections to a diverse range of topics, including deterministic
rounding schemes, pseudodeterminism, replicability, as well as Sperner/KKM-type
results.
  In this work, we establish near-optimal relationships between $k$ and
$\varepsilon$. We show that, for any bounded measure partitions and for any
$d\geq 1$, it must be that $k\geq(1+2\varepsilon)^d$. Thus, when $k=k(d)$ is
restricted to ${\rm poly}(d)$, it follows that $\varepsilon=\varepsilon(d)\in
O\left(\frac{\ln d}{d}\right)$. This bound is tight up to log factors, as it is
known that there exist secluded partitions with $k(d)=d+1$ and
$\varepsilon(d)=\frac{1}{2d}$. We also provide new constructions of secluded
partitions that work for a broad spectrum of $k(d)$ and $\varepsilon(d)$
parameters. Specifically, we prove that, for any
$f:\mathbb{N}\rightarrow\mathbb{N}$, there is a secluded partition with
$k(d)=(f(d)+1)^{\lceil\frac{d}{f(d)}\rceil}$ and
$\varepsilon(d)=\frac{1}{2f(d)}$. These new partitions are optimal up to
$O(\log d)$ factors for various choices of $k(d)$ and $\varepsilon(d)$. Based
on the lower bound result, we establish a new neighborhood version of Sperner's
lemma over hypercubes, which is of independent interest. In addition, we prove
a no-free-lunch theorem about the limitations of rounding schemes in the
context of pseudodeterministic/replicable algorithms.
