3
$\begingroup$

I would greatly appreciate some help/references on solving the following problem:

You are in charge of searching through a n-dimensional hyper-cube $[0,1]^n$ to make sure that it does not contain any defects. (To be precise, suppose we are given a black-box, Boolean function $D:[0,1]^n \to \{ 0,1\}$. A point $p \in [0,1]^n$ is said be defective if $D(p) = 1$. )

For any point $ p \in [0,1]^n$, you can find a ball of radius $ \epsilon(p)$ about that point, for which you are 100% confident there are no defects. The radius $\epsilon$ depends continuously on the point $p$ and is expensive to compute. (Alternatively, it may be better to just assume that the radius $\epsilon(p)$ is randomly chosen from an uniform probability distribution.)

How do you plan which points to check for nearby defects, so that you know when the entire hyper-cube has been covered by defect-free regions?

Improve this question
$\endgroup$
3
  • $\begingroup$ Hi Jonathan J., and welcome to scicomp! I'm a little confused. Define "defect" in the context of your problem. $\endgroup$
    – Paul
    Commented Jan 30, 2015 at 17:44
  • 1
    $\begingroup$ Seems like a pretty hard problem without further information. At the very minimum, the sum of the volumes of all the balls must be greater than the volume of the box (otherwise they could not possibly cover it). But the volume of a ball of radius $\epsilon$ goes as $\text{vol}=C(n)\epsilon^n$, so if $n$ is large you will need a huge number of balls. $\endgroup$
    – Nick Alger
    Commented Jan 30, 2015 at 23:03
  • $\begingroup$ This is $n$-dimensional minesweeper. $\endgroup$
    – Mark Hurd
    Commented Feb 5, 2015 at 2:15

1 Answer 1

Reset to default
1
$\begingroup$

Without knowing the actual values of $\varepsilon$ at the chosen points, the best you can hope to do is to take a probabilistic approach. Doing so will not lead to a guarantee that there are no defects, but a probability that you would have detected a defect if one were present.

One tactic would be to check a set of points corresponding to the centers of close-packed hyperspheres within your hypercube. The radius of the hyperspheres will depend on the desired confidence level as well as the distribution from which $\varepsilon$ is chosen. Based on this you could determine the expected volume fraction coverage of the hyperspheres and therefore the probability of detecting a defect if one exists.

As an alternative, if you know the probability distribution function (PDF) for $\varepsilon$ over your hypersphere (e.g. you know the variance of the normal distribution as a function of $p$) then it is probably possible to use random sampling based on a PDF where the probability of choosing a point in a given volume is proportional to one over the variance of the normal distribution corresponding to $\varepsilon$ (or something similar).

I'm not much of a stats/probability guy, but perhaps others can expand on this idea to provide additional quantitative details.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.