turkmath.org

Suppose we have “black-box” access to a set $A$ in $\mathbb{R}^n$ ; i.e., we can “query” points $x$ in $\mathbb{R}^n$ and learn whether or not they are in $A$. We would like to estimate the surface area of $A$. If we only make a few queries, it will be impossible to tell the difference between a nice set $A$ (like a ball) and a nice-set-with-an-extremely-high-surface-area-tentacle-of-volume-epsilon-glued-on. So we content ourselves with a weaker goal: we want to find a slight deformation $A^\prime$ of A satisfying vol$(A\Delta A^\prime)\leq\varepsilon$, as well as an accurate estimation of the surface area of $A^\prime$. We give an algorithm solving this problem in either Euclidean or Gaussian space and making roughly $\frac{1}{\varepsilon}$ queries. Surprisingly, the number of queries does not depend on the dimension $n$.