Smallest Enclosing Sphere (Min_sphere_d)

Definition

An object of the class Min_sphere_d<Traits> is the unique sphere of smallest volume enclosing a finite set of points in $$d-dimensional Euclidean space $$ _d. For a point set $$P we denote by $$ms(P) the smallest sphere that contains all points of $$P. Note that $$ms(P) can be degenerate, i.e. $$ms(P)=Ø$$ if $$P=Ø$$ and $$ms(P)={p} if $$P={p}.

An inclusion-minimal subset $$S of $$P with $$ms(S)=ms(P) is called a support set, the points in $$S are the support points. A support set has size at most $$d+1, and all its points lie on the boundary of $$ms(P). In general, neither the support set nor its size are necessarily unique.

The underlying algorithm can cope with all kinds of input, e.g. $$P may be empty or points may occur more than once. The algorithm computes a support set $$S which remains fixed until the next insert or clear operation.

Note: In this release correct results are only guaranteed if exact arithmetic is used.

#include <CGAL/Min_sphere_d.h>

Traits Class

The template parameter Traits is a traits class that defines the interface between the optimisation algorithm and the point class it uses.

We provide ready-to-use traits class implementations for 2D, 3D and dD CGAL points, see Section below.

Types

Min_sphere_d<Traits>::Traits

typedef Traits::Rep_tag
	Rep_tag;	Representation tag.
typedef Traits::NT	NT;	Number type.
typedef Traits::Point
	Point;	Point type.
typedef Traits::DA	DA;	Data accessor type.

See Section for the requirements these types have to fulfill.

The following defines iterator types for traversing the points resp. support points of the smallest enclosing sphere. Such iterators are non-mutable and their value type is Point. The iterator category is given in parentheses.

Min_sphere_d<Traits>::Point_iterator
	(bidirectional).
Min_sphere_d<Traits>::Support_point_iterator
	(bidirectional).

Guidelines and Hints

• For ultimate speed, use the representation tag Cartesian_tag and number type float or double, see the example below. For exact number types NT, we recommend the homogeneous representation, selected by using Homogeneous_tag, even if NT is a field type and supports divsions; the latter are usually slower than the other arithmetic operations, and it pays off to avoid them by using the homogeneous representation.

• The code is tuned for dimensions $$d 20. Expect a severe performance dropoff for larger dimensions.

• Because an object of the type Min_sphere_d<Traits> is of non-constant size, copy and assignment are expensive. Use references whenever possible.

Creation

Min_sphere_d<Traits> min_sphere ( Traits traits = Traits());
	creates a variable of type Min_sphere_d<Traits> and initializes it to $$ms(Ø$$).

A Min_sphere_d<Traits> object can be created from an arbitrary point set $$P, specified by an iterator range. All points must have the same dimension (see Section how the dimension of a point is accessed).

template < class InputIterator >
Min_sphere_d<Traits> min_sphere ( InputIterator first, InputIterator last, Traits traits = Traits());
	creates a variable min_sphere of type Min_sphere_d<Traits>. It is initialized to $$ms(P) with $$P being the set of points in the range [first,last). Precondition: The value type of first and last is Point, and all points have the same dimension.

Access Functions

int	min_sphere.number_of_points ()
		returns the number of points of min_sphere, i.e. $$|P|.
int	min_sphere.number_of_support_points ()
		returns the number of support points of min_sphere, i.e. $$|S|.
Point_iterator	min_sphere.points_begin ()
		returns an iterator referring to the first point of min_sphere.
Point_iterator	min_sphere.points_end ()
		returns the corresponding past-the-end iterator.
Support_point_iterator
	min_sphere.support_points_begin ()
		returns an iterator referring to the first support point of min_sphere.
Support_point_iterator
	min_sphere.support_points_end ()
		returns the corresponding past-the-end iterator.
int	min_sphere.ambient_dim ()
		returns the dimension of the points in $$P. If min_sphere is empty, the ambient dimension is $$-1.
Point	min_sphere.center ()
		returns the center of min_sphere. Precondition: min_sphere is not empty.
R::FT	min_sphere.squared_radius ()
		returns the squared radius of min_sphere. Precondition: min_sphere is not empty.

Predicates

By definition, an empty Min_sphere_d<Traits> has no boundary and no bounded side, i.e. its unbounded side equals the whole space $$ _d.

Bounded_side	min_sphere.bounded_side ( Point p)
		returns ON_BOUNDED_SIDE, ON_BOUNDARY, or ON_UNBOUNDED_SIDE iff p lies properly inside, on the boundary, or properly outside of min_sphere, resp. Precondition: if min_sphere is not empty, the dimension of $$p equals ambient_dim().
bool	min_sphere.has_on_bounded_side ( Point p)
		returns true, iff p lies properly inside min_sphere. Precondition: if min_sphere is not empty, the dimension of $$p equals ambient_dim().
bool	min_sphere.has_on_boundary ( Point p)
		returns true, iff p lies on the boundary of min_sphere. Precondition: if min_sphere is not empty, the dimension of $$p equals ambient_dim().
bool	min_sphere.has_on_unbounded_side ( Point p)
		returns true, iff p lies properly outside of min_sphere. Precondition: if min_sphere is not empty, the dimension of $$p equals ambient_dim().
bool	min_sphere.is_empty ()
		returns true, iff min_sphere is empty (this implies degeneracy).
bool	min_sphere.is_degenerate ()
		returns true, iff min_sphere is degenerate, i.e. if min_sphere is empty or equal to a single point, equivalently if the number of support points is less than 2.

Modifiers

void	min_sphere.clear ()
		resets min_sphere to $$ms(Ø$$).
template < class InputIterator >
void	min_sphere.set ( InputIterator first, InputIterator last)
		sets min_sphere to the $$ms(P), where $$P is the set of points in the range [first,last). Precondition: The value type of first and last is Point, and all points have the same dimension.
void	min_sphere.insert ( Point p)
		inserts p into min_sphere. If p lies inside the current sphere, this is a constant-time operation, otherwise it might take longer, but in any case substantially less than recomputing the smallest enclosing sphere from scratch. Precondition: The dimension of p equals ambient_dim() if min_sphere is not empty.
template < class InputIterator >
void	min_sphere.insert ( InputIterator first, InputIterator last)
		inserts the points in the range [first,last) into min_sphere and recomputes the smallest enclosing sphere, by calling insert for all points in the range. Precondition: The value type of first and last is Point, and all points have the same dimension. If min_sphere is not empty, this dimension must be equal to ambient_dim().

When applied to an empty min_sphere, set( first, last) and insert( first, last) produce the same result. However, the latter method is usually much slower, because it processes the points on-line, while the set method takes advantage of knowing the whole point set in advance.

Validity Check

An object min_sphere is valid, iff

• min_sphere contains all points of its defining set $$P,
• min_sphere is the smallest sphere containing its support set $$S, and
• $$S is minimal, i.e. no support point is redundant.

Note: Under inexact arithmetic, the result of the validation is not realiable, because the checker itself can suffer from numerical problems.

bool	min_sphere.is_valid ( bool verbose = false, int level = 0)
		returns true, iff min_sphere is valid. If verbose is true, some messages concerning the performed checks are written to standard error stream. The second parameter level is not used, we provide it only for consistency with interfaces of other classes.

Miscellaneous

Traits	min_sphere.traits ()
		returns a const reference to the traits class object.

I/O

ostream&	ostream& os << CGAL_Min_sphere_d<Traits> min_sphere
		writes min_sphere to output stream os. Precondition: The output operator is defined for Point.
istream&	istream& is >> CGAL_Min_sphere_d<Traits>& min_sphere
		reads min_sphere from input stream is. Precondition: The input operator is defined for Point.

See Also

Min_sphere_d_traits_2<R>, Min_sphere_d_traits_3<R>, Min_sphere_d_traits_d<R> , Min_circle_2 .

Implementation

We implement the algorithm of Welzl with move-to-front heuristic [Wel91] for small point sets, combined with a new efficient method for large sets, which is particularly tuned for moderately large dimension ($$d 20). The creation time is almost always linear in the number of points. Access functions and predicates take constant time, inserting a point might take up to linear time, but substantially less than computing the new smallest enclosing sphere from scratch. The clear operation and the check for validity each take linear time.

Example

The following program creates the smallest enclosing sphere of 10 points in dimension 5 and outputs it in pretty-print mode.

#include<CGAL/Cartesian.h>
#include<iostream>
#include<cstdlib>
#include<CGAL/Random.h>
#include<CGAL/Min_sphere_d.h>

using namespace CGAL;
using namespace std;

typedef Cartesian<double>                R;
typedef Min_sphere_d_traits_d<R>         Traits;
typedef Min_sphere_d<Traits>             Min_sphere;
typedef Point_d<R>                       Point;

const int n = 10;                        // number of points
const int d = 5;                         // dimension of points

int main ()
{
    Point         P[n];                  // n points
    double        coord[d];              // d coordinates
    Random        r;                     // random number generator

    for (int i=0; i<n; ++i) {
        for (int j=0; j<d; ++j)
            coord[j] = r.get_double();
        P[i] = Point(d, coord, coord+d); // random point
    }

    Min_sphere  ms (P, P+n);             // smallest enclosing sphere

    set_pretty_mode (cout);
    cout << ms;                          // output the sphere

    return 0;
}