Navigation: Up   Table of Contents   Package Overview   Bibliography   Index   Title   Acknowledging CGAL

CGAL::Min_sphere_d<Traits>

Definition

An object of the class Min_sphere_d<Traits> is the unique sphere of smallest volume enclosing a finite (multi)set of points in d-dimensional Euclidean space 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)=∅ 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 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<Traits> 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<Traits> is not reliable under floating-point computations. The only advantage of Min_sphere_d<Traits> 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<Traits> might still be an option in case your input number type cannot (efficiently) divide.

#include <CGAL/Min_sphere_d.h>

Requirements

The class Min_sphere_d<Traits> expects 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.

Types

Min_sphere_d<Traits>::Traits

Min_sphere_d<Traits>::FT
typedef to Traits::FT.


Min_sphere_d<Traits>::Point
typedef to Traits::Point.


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.

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.

Creation

Min_sphere_d<Traits> min_sphere ( Traits traits = Traits());
creates a variable of type Min_sphere_d<Traits> and initializes it to ms(∅). If the traits parameter is not supplied, the class Traits must provide a default constructor.


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).
Requirement: 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.

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_dimension () 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.

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 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().

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_dimension().

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_dimension().

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_dimension().

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).
Requirement: The value type of first and last is Point.
Precondition: 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 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 < 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.
Requirement: 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().

Validity Check

An object min_sphere is valid, iff

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

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

I/O

std::ostream& std::ostream& os << min_sphere writes min_sphere to output stream os.
Requirement: The output operator is defined for Point.

std::istream& std::istream& is >> min_sphere& reads min_sphere from input stream is.
Requirement: The input operator is defined for Point.

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 [Wel91] for small point sets, combined with a new efficient method for large sets, which is particularly tuned for moderately large dimension (d ≤ 20) [Gär99]. 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: examples/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_annulus_d_traits_d<K> Traits;
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;
}

Next: MinSphereAnnulusDTraits
Navigation: Up   Table of Contents   Package Overview   Bibliography   Index   Title   Acknowledging CGAL
CGAL Open Source Project. Release 3.5. 1 October 2009.