<p>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:</p>

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

CC BY-SA 3.0
2014-03-03T04:53:58.197Z
2014-03-03T04:53:58.197Z
Sariel Har-Peled
<p>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.</p>

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

CC BY-SA 3.0
2014-03-03T00:53:33.820Z
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
CC BY-SA 3.0
2014-03-03T06:36:20.820Z
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
<cg.comp-geom>
Largest embeddable hypersphere given membership oracle
PThomasCS
# Largest embeddable hypersphere given membership oracle

(Asked by: username_0 on 2014-03-03)

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

**Tags:** cg.comp-geom

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2014-03-03. Score: 5

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


---

