Bouncing Bubble Algorithm for smallest enclosing sphere

Question

I am interested in the Bouncing Bubble Algorithm to find the approximate smallest enclosing sphere for a set of points.

I understand the basic concept: "each time a point outside the ball is found, the ball will be moved towards it and increase the radius at the same time. The growth in each step is designed so that it will not exceed the optimum radius, thus the radius is getting closer and closer to the optimum."

I have however been unable to find anything more specific about it anywhere online. How is the growth calculated? How far is the shift towards the new point?

I am looking for either an example implementation or enough information to implement my own solution.

Answer 1

I realize this post is a year old, but I implemented the bouncing bubble algorithm in C++ and thought maybe some people would find it useful. This is based on the paper by Tian Bo, which I purchased for $18.

BoundSphere calculateBoundSphere(vector<Vertex> vertices){
    Vector3D center = vertices[0].position;
    float radius = 0.0001f;
    Vector3D pos, diff;
    float len, alpha, alphaSq;
    vector<Vertex>::iterator it;

    for (int i = 0; i < 2; i++){
        for (it = vertices.begin(); it != vertices.end(); it++){
            pos = it->position;
            diff = pos - center;
            len = diff.length();
            if (len > radius){
                alpha = len / radius;
                alphaSq = alpha * alpha;
                radius = 0.5f * (alpha + 1 / alpha) * radius;
                center = 0.5f * ((1 + 1 / alphaSq) * center + (1 - 1 / alphaSq) * pos);
            }
        }
    }

    for (it = vertices.begin(); it != vertices.end(); it++){
        pos = it->position;
        diff = pos - center;
        len = diff.length();
        if (len > radius){
            radius = (radius + len) / 2.0f;
            center = center + ((len - radius) / len * diff);
        }
    }

    return BoundSphere(center, radius);
}