Solving the bounding sphere problem
Computing the bounding sphere for a set of given vertices means solving the minimum covering circle problem in three dimensions. There're many algorithms out there to find such a bounding sphere, like Welzl's algorithm (at this page you can find an implementation in Java), and many others. You can also check out Fischer's exact solver the open source Miniball algorithm is based on.
The minimum enclosing sphere problem can be solved with an average algorithmic complexity of O(n4) for a naive algorithm working on free vertices, down to an easy O(nk) where k is the number of vertices of the equivalent convex hull of your starting mesh.
Edit: such linear-time solution is optimized for a convex set of vertices only, because further assumptions can be made due to geometric properties of convexity. A mesh with just no holes isn't necessarily convex; for example, a C-shaped mesh has no holes, but it isn't convex either – you can connect its two edges with a segment, and part of it will lie outside the shape. A solid mesh may have fewer vertices to compute compared to a "holed" counterpart (and the CPU will be happy about it), but solidity doesn't imply convexity. Thus such mesh isn't eligible for the optimized algorithm mentioned above.
Consideration: exact vs. approximate solutions
As developers, we should be aware of many aspects in our games. Highly-detailed simulations (e.g. physics) or rich graphics imply a greater workload on CPU/GPU; on the other hand, prioritizing performances excessively may lead to a poor game experience due to low quality of simulation.
As coders, we must not waste resources when possible; we can optimize some operations in order to spend spare resources elsewhere if needed. As designers, we must define the minimum requirements for our game without being too greedy: a side-scrolling platformer will never need the same precision of physics simulation we expect from a top-quality racing game.
We need tradeoffs between results expected and resources required; every CPU clock is precious. If we can sacrifice some little realism without having the player noticing it and gain overall performances, this is a good way to go in my opinion.
An approximate, efficient algorithm
Having already aswered your question, if you don't really need the smallest sphere possible and an approximation of it is good enough, you can go with this algorithm.
algorithm MiniBall
input: set V of points in space
output: enclosing sphere in the form [center, radius]
B = AABB(V) // AABB from vertices
C = mean(B.max + B.min) // centroid of box B
for each v in V:
r = max(r, dist(C, v)) // distance to furthest point
return [C, r]
The main idea is:
Consider the axis-aligned bounding-box, and use its centroid as origin. This ensures the sphere center will be always amongst the vertices;
Find the distance from the centroid to the furthest vertex, and use such distance as radius. This ensures that no points will lie outside of the sphere, at most on the sphere surface.
The complexity of this algorithm is O(n) where n is the number of vertices: you first read all vertices to find the bounding box corners, then you compute n distances between centroid and individual vertices.
It's quite fast, and may be more suitable for a real-time application with average precision requirements, such as a videogame.
Bonus: you can tweak the code line computing distance, and use the criterion that better suits your needs:
Max distance: no points outside of the sphere, at least one on the surface;
Min distance: no points inside the sphere, at least one on the surface (not really recommended in most cases);
Average distance: compute both the larger and smaller radii, and use mean(minR, maxR) as sphere radius. On average the sphere will split the vertices set into two halves. Some points may be inside the sphere, others outside of it, some can lie on the surface.
