If I have a polytope (e.g. the feasible set of some $Ax \leq b$ where the result is closed), do there exist efficient algorithms for finding the minimum enclosing ball in $d$ dimensions? In other words, solving for: $$ \min_{c \in \mathcal{R}^d, r \geq 0} r\\ s.t.\\ ||x - c||_p \leq r,\ \forall x \in \mathcal{R}^d: Ax \leq b $$ Any $p$ would be fine here, of obvious interest are: $p=1$, $p=2$, or $p=\infty$.
Of course, one can represent this is a minimax problem: $$ r = \min_{c \in \mathcal{R}^d} \max_{x \in \mathcal{R}^d: Ax \leq b} ||x - c||_p $$
Note that I don't have the vertices of the polytope, only $A$ and $b$.
No, nothing efficient in H-representation. As you already seem to know, with vertices it is simple, but the step of going from half-plane representation to vertices might be intractable.
EDIT: $p = \infty$ is tractable, as you can address that case using duality in a polynomially sized linear program.
EDIT2: No reason to complicate matters when $p=\infty$. It simply corresponds to a weak bounding box of the polytope, which can be computed by solving $2d$ linear programs.