\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.5 - Bounding Volumes
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::Min_sphere_d< Traits > Class Template Reference

#include <CGAL/Min_sphere_d.h>

Definition

An object of the class Min_sphere_d is the unique sphere of smallest volume enclosing a finite (multi)set of points in \( d\)-dimensional Euclidean space \( \E^d\).

For a set \( P\) we denote by \( ms(P)\) the smallest sphere that contains all points of \( P\). \( ms(P)\) can be degenerate, i.e. \( ms(P)=\emptyset\) if \( P=\emptyset\) 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 unique.

The algorithm computes a support set \( S\) which remains fixed until the next insert or clear operation.

Please note: This class is (almost) obsolete. The class CGAL::Min_sphere_of_spheres_d<Traits> solves a more general problem and is faster then Min_sphere_d even if used only for points as input. Most importantly, CGAL::Min_sphere_of_spheres_d<Traits> has a specialized implementation for floating-point arithmetic which ensures correct results in a large number of cases (including highly degenerate ones). In contrast, Min_sphere_d is not reliable under floating-point computations. The only advantage of Min_sphere_d over CGAL::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, Min_sphere_d might still be an option in case your input number type cannot (efficiently) divide.

Template Parameters
Traitsmust be a model of the concept OptimisationDTraits as its template argument.

We provide the models CGAL::Optimisation_d_traits_2, CGAL::Optimisation_d_traits_3 and CGAL::Optimisation_d_traits_d for two-, three-, and \( d\)-dimensional points respectively.

See Also
CGAL::Optimisation_d_traits_2<K,ET,NT>
CGAL::Optimisation_d_traits_3<K,ET,NT>
CGAL::Optimisation_d_traits_d<K,ET,NT>
OptimisationDTraits
CGAL::Min_circle_2<Traits>
CGAL::Min_sphere_of_spheres_d<Traits>
CGAL::Min_annulus_d<Traits>

Implementation

We implement the algorithm of Welzl with move-to-front heuristic [16] for small point sets, combined with a new efficient method for large sets, which is particularly tuned for moderately large dimension ( \( d \leq 20\)) [8]. 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


File Min_sphere_d/min_sphere_d.cpp

#include <CGAL/Cartesian_d.h>
#include <iostream>
#include <cstdlib>
#include <CGAL/Random.h>
#include <CGAL/Min_sphere_annulus_d_traits_d.h>
#include <CGAL/Min_sphere_d.h>
typedef CGAL::Cartesian_d<double> K;
typedef CGAL::Min_sphere_d<Traits> Min_sphere;
typedef K::Point_d 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
CGAL::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
CGAL::set_pretty_mode (std::cout);
std::cout << ms; // output the sphere
return 0;
}
Examples:
Min_sphere_d/min_sphere_d.cpp.

Related Functions

(Note that these are not member functions.)

std::ostream & operator<< (std::ostream &os, const Min_sphere_d< Traits > &min_sphere)
 writes min_sphere to output stream os. More...
 
std::istream & operator>> (std::istream &is, Min_sphere_d< Traits > min_sphere &)
 reads min_sphere from input stream is. More...
 

Types

typedef unspecified_type FT
 typedef to Traits::FT.
 
typedef unspecified_type Point
 typedef to Traits::Point.
 
typedef unspecified_type Point_iterator
 non-mutable model of the STL concept BidirectionalIterator with value type Point. More...
 
typedef unspecified_type Support_point_iterator
 non-mutable model of the STL concept BidirectionalIterator with value type Point. More...
 

Creation

 Min_sphere_d (const Traits &traits=Traits())
 creates a variable of type Min_sphere_d and initializes it to \( ms(\emptyset)\). More...
 
template<class InputIterator >
 Min_sphere_d (InputIterator first, InputIterator last, const Traits &traits=Traits())
 creates a variable min_sphere of type Min_sphere_d. More...
 
int number_of_points () const
 returns the number of points of min_sphere, i.e. \( |P|\).
 
int number_of_support_points () const
 returns the number of support points of min_sphere, i.e. \( |S|\).
 
Point_iterator points_begin () const
 returns an iterator referring to the first point of min_sphere.
 
Point_iterator points_end () const
 returns the corresponding past-the-end iterator.
 
Support_point_iterator support_points_begin () const
 returns an iterator referring to the first support point of min_sphere.
 
Support_point_iterator support_points_end () const
 returns the corresponding past-the-end iterator.
 
int ambient_dimension () const
 returns the dimension of the points in \( P\). More...
 
const Pointcenter () const
 returns the center of min_sphere. More...
 
FT squared_radius () const
 returns the squared radius of min_sphere. More...
 

Predicates

By definition, an empty Min_sphere_d has no boundary and no bounded side, i.e. its unbounded side equals the whole space \( \E^d\).

Bounded_side bounded_side (const Point &p) const
 returns CGAL::ON_BOUNDED_SIDE, CGAL::ON_BOUNDARY, or CGAL::ON_UNBOUNDED_SIDE iff p lies properly inside, on the boundary, or properly outside of min_sphere, resp. More...
 
bool has_on_bounded_side (const Point &p) const
 returns true, iff p lies properly inside min_sphere. More...
 
bool has_on_boundary (const Point &p) const
 returns true, iff p lies on the boundary of min_sphere. More...
 
bool has_on_unbounded_side (const Point &p) const
 returns true, iff p lies properly outside of min_sphere. More...
 
bool is_empty () const
 returns true, iff min_sphere is empty (this implies degeneracy).
 
bool is_degenerate () const
 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 clear ()
 resets min_sphere to \( ms(\emptyset)\).
 
template<class InputIterator >
void set (InputIterator first, InputIterator last)
 sets min_sphere to the \( ms(P)\), where \( P\) is the set of points in the range [first,last). More...
 
void insert (const Point &p)
 inserts p into min_sphere. More...
 
template<class InputIterator >
void 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. More...
 

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 is_valid (bool verbose=false, int level=0) const
 returns true, iff min_sphere is valid. More...
 

Miscellaneous

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

Member Typedef Documentation

template<typename Traits >
typedef unspecified_type CGAL::Min_sphere_d< Traits >::Point_iterator

non-mutable model of the STL concept BidirectionalIterator with value type Point.

Used to access the points used to build the smallest enclosing sphere.

template<typename Traits >
typedef unspecified_type CGAL::Min_sphere_d< Traits >::Support_point_iterator

non-mutable model of the STL concept BidirectionalIterator with value type Point.

Used to access the support points defining the smallest enclosing sphere.

Constructor & Destructor Documentation

template<typename Traits >
CGAL::Min_sphere_d< Traits >::Min_sphere_d ( const Traits traits = Traits())

creates a variable of type Min_sphere_d and initializes it to \( ms(\emptyset)\).

If the traits parameter is not supplied, the class Traits must provide a default constructor.

template<typename Traits >
template<class InputIterator >
CGAL::Min_sphere_d< Traits >::Min_sphere_d ( InputIterator  first,
InputIterator  last,
const Traits traits = Traits() 
)

creates a variable min_sphere of type Min_sphere_d.

It is initialized to \( ms(P)\) with \( P\) being the set of points in the range [first,last).

Requires:
The value type of first and last is Point. If the traits parameter is not supplied, the class Traits must provide a default constructor.
Precondition
All points have the same dimension.

Member Function Documentation

template<typename Traits >
int CGAL::Min_sphere_d< Traits >::ambient_dimension ( ) const

returns the dimension of the points in \( P\).

If min_sphere is empty, the ambient dimension is \( -1\).

template<typename Traits >
Bounded_side CGAL::Min_sphere_d< Traits >::bounded_side ( const Point p) const

returns CGAL::ON_BOUNDED_SIDE, CGAL::ON_BOUNDARY, or CGAL::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_dimension().
template<typename Traits >
const Point& CGAL::Min_sphere_d< Traits >::center ( ) const

returns the center of min_sphere.

Precondition
min_sphere is not empty.
template<typename Traits >
bool CGAL::Min_sphere_d< Traits >::has_on_boundary ( const Point p) const

returns true, iff p lies on the boundary of min_sphere.

Precondition
if min_sphere is not empty, the dimension of \( p\) equals ambient_dimension().
template<typename Traits >
bool CGAL::Min_sphere_d< Traits >::has_on_bounded_side ( const Point p) const

returns true, iff p lies properly inside min_sphere.

Precondition
If min_sphere is not empty, the dimension of \( p\) equals ambient_dimension().
template<typename Traits >
bool CGAL::Min_sphere_d< Traits >::has_on_unbounded_side ( const Point p) const

returns true, iff p lies properly outside of min_sphere.

Precondition
If min_sphere is not empty, the dimension of \( p\) equals ambient_dimension().
template<typename Traits >
void CGAL::Min_sphere_d< Traits >::insert ( const 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 usually substantially less than recomputing the smallest enclosing sphere from scratch.

Precondition
The dimension of p equals ambient_dimension() if min_sphere is not empty.
template<typename Traits >
template<class InputIterator >
void CGAL::Min_sphere_d< Traits >::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.

Requires:
The value type of first and last is Point.
Precondition
All points have the same dimension. If min_sphere is not empty, this dimension must be equal to ambient_dimension().
template<typename Traits >
bool CGAL::Min_sphere_d< Traits >::is_valid ( bool  verbose = false,
int  level = 0 
) const

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.

template<typename Traits >
template<class InputIterator >
void CGAL::Min_sphere_d< Traits >::set ( InputIterator  first,
InputIterator  last 
)

sets min_sphere to the \( ms(P)\), where \( P\) is the set of points in the range [first,last).

Requires:
The value type of first and last is Point.
Precondition
All points have the same dimension.
template<typename Traits >
FT CGAL::Min_sphere_d< Traits >::squared_radius ( ) const

returns the squared radius of min_sphere.

Precondition
min_sphere is not empty.

Friends And Related Function Documentation

template<typename Traits >
std::ostream & operator<< ( std::ostream &  os,
const Min_sphere_d< Traits > &  min_sphere 
)
related

writes min_sphere to output stream os.

Requires:
The output operator is defined for Point.
template<typename Traits >
std::istream & operator>> ( std::istream &  is,
Min_sphere_d< Traits > min_sphere &   
)
related

reads min_sphere from input stream is.

Requires:
The input operator is defined for Point.