CGAL::Min_sphere_of_spheres_d<Traits>

Definition

An object of the class Min_sphere_of_spheres_d<Traits> is a data structure that represents the unique sphere of smallest volume enclosing a finite set of spheres in d-dimensional Euclidean space ^d. For a set S of spheres we denote by ms(S) the smallest sphere that contains all spheres of S; we call ms(S) the minsphere of S. ms(S) can be degenerate, i.e., ms(S)=∅, if S=∅ and ms(S)={s}, if S={s}. Any sphere in S may be degenerate, too, i.e., any sphere from S may be a point. Also, S may contain several copies of the same sphere.

An inclusion-minimal subset R of S with ms(R)=ms(S) is called a support set for ms(S); the spheres in R are the support spheres. A support set has size at most d+1, and all its spheres lie on the boundary of ms(S). (A sphere s' is said to lie on the boundary of a sphere s, if s' is contained in s and if their boundaries intersect.) In general, the support set is not unique.

The algorithm computes the center and the radius of ms(S), and finds a support set R (which remains fixed until the next insert(), clear() or set() operation). We also provide a specialization of the algorithm for the case when the center coordinates and radii of the input spheres are floating-point numbers. This specialized algorithm uses floating-point arithmetic only, is very fast and especially tuned for stability and robustness. Still, it's output may be incorrect in some (rare) cases; termination is guaranteed.

When default constructed, an instance of type Min_sphere_of_spheres_d<Traits> represents the set S=∅, together with its minsphere ms(S)=∅. You can add spheres to the set S by calling insert(). Querying the minsphere is done by calling the routines is_empty(), radius() and center_cartesian_begin(), among others.

In general, the radius and the Euclidean center coordinates of ms(S) need not be rational. Consequently, the algorithm computing the exact minsphere will have to deal with algebraic numbers. Fortunately, both the radius and the coordinates of the minsphere are numbers of the form a_i+b_i√t, where a_i,b_i,t ∈ ℚ and where t ≥ 0 is the same for all coordinates and the radius. Thus, the exact minsphere can be described by the number t, which is called the sphere's discriminant, and by d+1 pairs (a_i,b_i) ∈ ℚ² (one for the radius and d for the center coordinates).

#include <CGAL/Min_sphere_of_spheres_d.h>

Note: This class (almost) replaces CGAL::Min_sphere_d<Traits>, which solves the less general problem of finding the smallest enclosing ball of a set of points. Min_sphere_of_spheres_d<Traits> is faster than CGAL::Min_sphere_d<Traits>, and in contrast to the latter provides a specialized implementation for floating-point arithmetic which ensures correct results in a large number of cases (including highly degenerate ones). The only advantage of CGAL::Min_sphere_d<Traits> over Min_sphere_of_spheres_d<Traits> is that the former can deal with points in homogeneous coordinates, in which case the algorithm is division-free. Thus, CGAL::Min_sphere_d<Traits> might still be an option in case your input number type cannot (efficiently) divide.

Requirements

The class Min_sphere_of_spheres_d<Traits> expects a model of the concept MinSphereOfSpheresTraits as its template argument.

Types

Creation

Access Functions

Predicates

Modifiers

Validity Check

• minsphere contains all spheres of its defining set S,
• minsphere is the smallest sphere containing its support set R, and
• R is minimal, i.e., no support sphere is redundant.

Miscellaneous

See Also

Implementation

We implement two algorithms, the LP-algorithm and a heuristic [MSW92]. As described in the documentation of concept MinSphereOfSpheresTraits, each has its advantages and disadvantages: Our implementation of the LP-algorithm has maximal expected running time O(2^d n), while the heuristic comes without any complexity guarantee. In particular, the LP-algorithm runs in linear time for fixed dimension d. (These running times hold for the arithmetic model, so they count the number of operations on the number type FT.)

On the other hand, the LP-algorithm is, for inexact number types FT, much worse at handling degeneracies and should therefore not be used in such a case. (For exact number types FT, both methods handle all kinds of degeneracies.)

Currently, we require Traits::FT to be either an exact number type or double or float; other inexact number types are not supported at this time. Also, the current implementation only handles spheres with Cartesian coordinates; homogenous representation is not supported yet.

Example

File: examples/Min_sphere_of_spheres_d/min_sphere_of_spheres_d_d.cpp

#include <CGAL/Cartesian_d.h>
#include <CGAL/Random.h>
#include <CGAL/Gmpq.h>
#include <CGAL/Min_sphere_of_spheres_d.h>
#include <vector>

const int N = 1000;                       // number of spheres
const int D = 3;                          // dimension of points
const int LOW = 0, HIGH = 10000;          // range of coordinates and radii

typedef CGAL::Gmpq                        FT;
//typedef double                          FT;
typedef CGAL::Cartesian_d<FT>             K;
typedef CGAL::Min_sphere_of_spheres_d_traits_d<K,FT,D> Traits;
typedef CGAL::Min_sphere_of_spheres_d<Traits> Min_sphere;
typedef K::Point_d                        Point;
typedef Traits::Sphere                    Sphere;

int main () {
  std::vector<Sphere> S;                  // n spheres
  FT coord[D];                            // d coordinates
  CGAL::Random r;                         // random number generator

  for (int i=0; i<N; ++i) {
    for (int j=0; j<D; ++j)
      coord[j] = r.get_int(LOW,HIGH);
    Point p(D,coord,coord+D);             // random center...
    S.push_back(Sphere(p,r.get_int(LOW,HIGH))); // ...and random radius
  }

  Min_sphere ms(S.begin(),S.end());       // check in the spheres
  CGAL_assertion(ms.is_valid());
}