Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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).

share|improve this question
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 at 0:53
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 at 6:36
add comment

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

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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