Largest embeddable hypersphere given membership oracle
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