Geometric Optimisation

Introduction

This chapter describes routines for solving geometric optimisation problems.

The first three sections contain algorithms for computing and updating the

• smallest enclosing circle (2D) (Section ), the
• smallest enclosing ellipse (2D) (Section ), and the
• smallest enclosing sphere (dD) (Section ), respectively,

Section  describes several functions to compute the smallest enclosing region $$r of a planar convex polygon $$P where $$r is to be chosen from a set $$ of candidate regions.

The remaining sections describe algorithms for searching in matrices with specific properties and some applications. In particular, there are general implementations of

• monotone matrix search (Section ), which can be applied to compute
  • extremal polygons of a convex polygon (Section ) or
  • all furthest neighbors for the vertices of a convex polygon (Section ),
• and sorted matrix search (Section ), which can be used to compute the $$p-centers of a planar point set (Section ).

Traits Class

Assertions

Smallest Enclosing Circles

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.

• Class declaration of Min_circle_2<Traits>.

• Class declaration of Optimisation_circle_2<R>.

• Class declaration of Min_circle_2_traits_2<R>.

• Class declaration of Min_circle_2_adapterC2<PT,DA>.

• Class declaration of Min_circle_2_adapterH2<PT,DA>.

• Requirements of Traits Class Adapters to 2D Cartesian Points.

• Requirements of Traits Class Adapters to 2D Homogeneous Points.

• Requirements of Traits Classes for 2D Smallest Enclosing Circle.

Smallest Enclosing Ellipses

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.

• Class declaration of Min_ellipse_2<Traits>.

• Class declaration of Optimisation_ellipse_2<R>.

• Class declaration of Min_ellipse_2_traits_2<R>.

• Class declaration of Min_ellipse_2_adapterC2<PT,DA>.

• Class declaration of Min_ellipse_2_adapterH2<PT,DA>.

• Requirements of Traits Class Adapters to 2D Cartesian Points.

• Requirements of Traits Class Adapters to 2D Homogeneous Points.

• Requirements of Traits Classes for 2D Smallest Enclosing Ellipse.

Smallest Enclosing Spheres

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 volume 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.

• Class declaration of Min_sphere_d<Traits>.

• Default Traits Classes for Smallest Enclosing Sphere.

• Requirements of Traits Classes for Smallest Enclosing Sphere.

Minimum Enclosing Quadrilaterals

This section describes several functions to compute the smallest enclosing region $$r of a planar convex polygon $$P where $$r is to be chosen from a set $$ of candidate regions.

• Function Declaration of minimum_enclosing_rectangle_2.

• Function Declaration of minimum_enclosing_parallelogram_2.

• Function Declaration of minimum_enclosing_strip_2.

• Class declaration of Minq_traits.

Computing Extremal Polygons

This section describes several functions to compute a maximal $$k-gon $$P_k that can be inscribed into a given convex polygon $$P. 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 $$k-gon.

• Function Declaration of maximum_area_inscribed_k_gon.

• Function Declaration of maximum_perimeter_inscribed_k_gon.

• Function Declaration of extremal_polygon.

• Class declaration of Exp_traits.

All Furthest Neighbors

This section describes a function to compute all furthest neighbors for the vertices of a convex polygon.

• Definition of function all_furthest_neighbors.

• Class declaration of Afn_traits.

Rectangular $$p-Centers

This section describes a function to compute rectilinear $$p-centers of a planar point set, i.e. a set of $$p points such that the maximum minimal distance between both sets is minimized.

• Definition of function rectangular_p_center_2.

• Class declaration of Rpc_traits.

Monotone Matrix Search

In this section we describe a general function to compute the maxima for all rows of a totally monotone matrix.

• Function Declaration of monotone_matrix_search.

• Class declaration of Mms_matrix.

• Class declaration of Dynamic_matrix<M>.

• Class declaration of BasicMatrix.

Sorted Matrix Search

This section describes a general function to select the smallest entry in a set of sorted matrices that fulfills a certain criterion.

• Function Declaration of sorted_matrix_search.

• Class declaration of Sms_traits.

• Class declaration of Sorted_matrix_search_traits_adaptor<F,M>.