Welzl's Minimum Sphere Algorithm Demystified
by Eli Kara

Contents   Page 1   Page 2   Page 3   Page 4   Source code   Printable version   Discuss this article

Introduction

Spheres are among the most common geometric entities used in performing various game engine related tasks such as object culling, containment, bounding volumes and bounding volume hierarchies to name a few.

Spheres are excellent candidates for bounding volumes and are widely used mainly because they have inexpensive intersection tests, are easy to transform (they are rotation-invariant) and have small memory usage.

Unfortunately, axis-aligned bounding boxes are often preferred over spheres due to fitting problems or the fact that a tight fitting sphere is hard to compute in real time. In this article we'll explore what is considered the optimal solution to the sphere fitting problem, a solution proposed by Emo Welzl [Welzl91]. For simplicity we'll limit ourselves to the discussion and implementation of the algorithm in 2D only, although the algorithm scales quite nicely to 3D.

A simple Java-based implementation of the sphere generation algorithm is provided. The code is described later on in the article.

The problem of finding an optimal sphere

There are many algorithms to compute an enclosing sphere of a set of points. Most of the algorithms may be easy to implement and understand but fail to provide optimal spheres in most cases.

A description of some of the basic algorithms and their shortcomings is listed below:

• The mean of the input points – This very simple and linear algorithm is the simplest of all but can give extremely bad results due to point clustering. The sphere can have up to twice the optimal radius. Clearly this is not the way to go.
• A sphere contained within an AABB – A simple approximation is to find the AABB enclosing all points and obtaining the midpoint (the sphere's center) and the radius to be the distance from this center to the farthest point. While this approach is fairly simple and provides adequate results, it does not compare to the optimal solution.
• Computing a sphere using maximum spread – This approach attempts to find the axis direction of the maximum spread of the input points and uses it as the diameter of the sphere. The points most extreme on the axis are selected and the center is set halfway between them. Although an interesting approach, it suffers from problems due to point clustering and internal points ruining the covariance.
• Brute force – Since a sphere in 3D is uniquely defined by four points (two in 2D), a simple brute force approach might attempt to find the minimum sphere by trying all combination of spheres made up by four points, three points and two points, keeping the minimum-sized sphere that contains all points. This approach is the worst with a running complexity of O(n5).

Page 2