An object of the class Min_annulus_d<Traits> is the unique annulus (region between two concentric spheres with radii $$r and $$R, $$r R) enclosing a finite set of points in $$ddimensional Euclidean space $$ _{d}, where the difference $$R^{2}r^{2} is minimal. For a point set $$P we denote by $$ma(P) the smallest annulus that contains all points of $$P. Note that $$ma(P) can be degenerate, i.e. $$ma(P)=Ø$$ if $$P=Ø$$ and $$ma(P)={p} if $$P={p}.
An inclusionminimal subset $$S of $$P with $$ma(S)=ma(P) is called a support set, the points in $$S are the support points. A support set has size at most $$d+2, and all its points lie on the boundary of $$ma(P). In general, the support set is not 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 set, insert, or clear operation.
#include <CGAL/Min_annulus_d.h>
The template parameter Traits is a model for OptimisationDTraits.
We provide the models Optimisation_d_traits_2, Optimisation_d_traits_3, and Optimisation_d_traits_d using the two, three, and $$ddimensional CGAL kernel, respectively.
 
typedef to Traits::Point_d.
Point type used to represent the input points.
 
 
typedef to Traits::FT.
Number type used to return the squared radii of the smallest
enclosing annulus.
 
 
typedef to Traits::ET.
Number type used to do the exact computations in the underlying
solver for quadratic programs (cf. Implementation).
 
 
nonmutable model of the STL concept RandomAccessIterator
with value type Point. Used to access the points
of the smallest enclosing annulus.
 
 
nonmutable model of the STL concept RandomAccessIterator
with value type Point. Used to access the support points
of the smallest enclosing annulus.
 
 
nonmutable model of the STL concept RandomAccessIterator
with value type Point. Used to access the inner support points
of the smallest enclosing annulus.
 
 
nonmutable model of the STL concept RandomAccessIterator
with value type Point. Used to access the outer support points
of the smallest enclosing annulus.
 
 
nonmutable model of the STL concept RandomAccessIterator
with value type ET. Used to access the coordinates of
the center of the smallest enclosing annulus.

 
initializes min_annulus to $$ma(Ø$$).
 
 
 
initializes min_annulus to $$ma(P) with $$P being the set of points
in the range [first,last). Requirement: The value type of InputIterator is Point. Precondition: All points have the same dimension.

advanced 
advanced 

 
returns an iterator referring to the first point of min_annulus.  

 
returns the corresponding pasttheend iterator. 
The bounded area of the smallest enclosing annulus lies between the inner and the outer sphere. The boundary is the union of both spheres. By definition, an empty annulus has no boundary and no bounded side, i.e. its unbounded side equals the whole space $$ _{d}.

 
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_annulus, resp. Precondition: The dimension of p equals min_annulus.ambient_dimension() if min_annulus is not empty.  

 
returns true, iff p lies properly inside min_annulus. Precondition: The dimension of p equals min_annulus.ambient_dimension() if min_annulus is not empty.  

 
returns true, iff p lies on the boundary of min_annulus. Precondition: The dimension of p equals min_annulus.ambient_dimension() if min_annulus is not empty.  

 
returns true, iff p lies properly outside of min_annulus. Precondition: The dimension of p equals min_annulus.ambient_dimension() if min_annulus is not empty.  

 
returns true, iff min_annulus is empty (this implies degeneracy).  

 
returns true, iff min_annulus is degenerate, i.e. if min_annulus is empty or equal to a single point. 
An object min_annulus is valid, iff

 
returns true, iff min_annulus 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. 

 
returns a const reference to the traits class object. 

 
writes min_annulus to output stream os. Requirement: The output operator is defined for Point. 

 
reads min_annulus from input stream is. Requirement: The input operator is defined for Point. 
CGAL::Min_sphere_d<Traits>
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
The problem of finding the smallest enclosing annulus of a finite point set can be formulated as an optimization problem with linear constraints and a linear objective function. The solution is obtained using our exact solver for linear and quadratic programs [GS00].
The creation time is almost always linear in the number of points. Access functions and predicates take constant time, inserting a point takes almost always linear time. The clear operation and the check for validity each take linear time.