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
    $\begingroup$ 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. $\endgroup$ Commented Mar 3, 2014 at 0:53
  • 1
    $\begingroup$ 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. $\endgroup$
    – R B
    Commented Mar 3, 2014 at 6:36

1 Answer 1


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

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.