Geometry of a Set and its Random Covers

Let $E$ be a bounded open subset of $\bbR^\dmn$. We study the following questions: For i.i.d.~samples $X_1, \dots, X_N$ drawn uniformly from $E$, what is the probability that $\cup_i \bfB(X_i, \delta)$, the union of $\delta$-balls centered at $X_i$, covers $E$? And how does the probability depend on sample size $N$ and the radius of balls $\delta$? We present geometric conditions of $E$ under which we derive lower bounds to this probability. These lower bounds tend to $1$ as a function of $\exp{(-\delta^\dmn N)}$.\\The basic tool that we use to derive the lower bounds is a \emph{good} partition of $E$, i.e., one whose partition elements have diameters that are uniformly bounded from above and have volumes that are uniformly bounded from below. We show that if $E^c$, the complement of $E$, has positive reach then we can construct a good partition of $E$. This partition is motivated by the Whitney decomposition of $E$. On the other hand, we identify a class of bounded open subsets of $\bbR^\dmn$ that do not satisfy this positive reach condition but do have good partitions.\\ In 2D when $E^c\subset \bbR^2$ does not have positive reach, we show that the \emph{mutliscale flat norm} can be used to approximate $E$ with a set that has a good partition under certain conditions. In this case, we provide a lower bound on the probability that the union of the balls \emph{almost} covers $E$.