I have a membership oracle to tell me whether a point is inside of some set, S. I would like to find the radius of the largest (origin-centered) hypersphere that is contained in S.

Do you know any good references for this problem? (I'm looking for an algorithm along with a confidence that the hypersphere is fully contained in S).

  • 3
    Without more knowledge of the structure of $S$, the problem is impossible. For example, if we're inside $\mathbb{R}^n$, and $S = \mathbb{R}^n - B$ for $B$ a countable set of independent Gaussian samples, all oracle queries will say yes but the maximum radius is 0. – Geoffrey Irving Mar 3 '14 at 0:53
  • 1
    Even if S is connected, without further assumptions, the VC dimension of the possible sets is infinite, therefore not learnable from any number of queries. – R B Mar 3 '14 at 6:36

If S is convex, that this is a linear programming problem. It can as such be solved/approximated in polynomial time using the standard sequence of reductions to the ellipsoid algorithm. I do not know any reference that describe it cleanly, but the following book describe it:

Geometric Algorithms and Combinatorial Optimization (Algorithms and Combinatorics) [Paperback] Martin Grötschel, Laszlo Lovasz, Alexander Schrijver

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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