Geometric Optimisation

This chapter describes routines for solving geometric optimisation problems.

There are algorithms for computing and updating the

• smallest enclosing circle (Min_circle_2<Traits>), the
• smallest enclosing ellipse (Min_ellipse_2<Traits>), the
• smallest enclosing sphere (Min_sphere_d<Traits>), and the
• smallest enclosing annulus (Min_annulus_d<Traits>), respectively,

We provide 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 (min_rectangle_2, min_parallelogram_2, min_strip_2).

An algorithm for computing and updating the (squared) distance of two convex polytopes is described (Polytope_distance_d).

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

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