This chapter describes routines for solving geometric optimisation problems. The first three sections contain algorithms for computing and updating the
This section describes routines for computing and updating the smallest enclosing circle of a finite point set. Formally, the `smallest enclosing circle' is the boundary of the closed disk of minimum area covering the point set. It is known that this disk is unique. We usually identify the disk with its bounding circle, allowing us to talk about points being on the boundary of the circle, etc.
The algorithm works in an incremental manner. It is implemented as a semi-dynamic data structure, thus allowing to insert points while maintaining the smallest enclosing circle.
This section describes routines for computing and updating the smallest enclosing ellipse of a finite point set. Formally, the `smallest enclosing ellipse' is the boundary of the closed disk of minimum area covering the point set. It is known that this disk is unique. We usually identify the disk with its bounding ellipse, allowing us to talk about points being on the boundary of the ellipse, etc.
The algorithm works in an incremental manner. It is implemented as a semi-dynamic data structure, thus allowing to insert points while maintaining the smallest enclosing ellipse.
This section describes routines for computing and updating the smallest enclosing sphere of a finite point set. Formally, the `smallest enclosing sphere' is the boundary of the closed ball of minimum area covering the point set. It is known that this ball is unique. We usually identify the ball with its bounding sphere, allowing us to talk about points being on the boundary of the sphere, etc.
The algorithm is implemented as a semi-dynamic data structure, thus allowing to insert points while maintaining the smallest enclosing sphere.
This section describes several functions to compute a maximal -gon that can be inscribed into a given convex polygon . The criterion for maximality can be chosen freely by defining an appropriate traits class as specified in section . For CGAL point classes there are two predefined traits classes to compute a maximum area (see section ) resp. perimeter (see section ) inscribed -gon.
This section describes a function to compute all furthest neighbors for the vertices of a convex polygon.
This section describes a function to compute rectilinear -centers of a planar point set, i.e. a set of points such that the maximum minimal distance between both sets is minimized.
In this section we describe a general function to compute the maxima for all rows of a totally monotone matrix.
This section describes a general function to select the smallest entry in a set of sorted matrices that fulfills a certain criterion.