Chapter 52
Geometric Optimisation

Introduction

This chapter describes concepts, classes, and functions for solving geometric optimisation problems. They are divided into four categories.

Bounding Areas and Volumes. Smallest enclosing circle and ellipse (2D), smallest enclosing rectangle, parallelogram, and strip (2D), rectangular $$p-center (2D), smallest enclosing sphere and annulus (dD).

Inscribed Areas. Maximum area and perimeter inscribed $$k-gon (2D), extremal inscribed $$k-gon (2D), largest empty isorectangle (2D).

Optimal Distances. All furthest neigbors (2D), width of point set (3D), polytope distance (dD).

Advanced Techniques. Monotone and sorted matrix search.

Assertions

Bounding Areas and Volumes

CGAL::Min_circle_2<Traits>
CGAL::Min_circle_2_traits_2<K>
MinCircle2Traits

CGAL::Min_ellipse_2<Traits>
CGAL::Min_ellipse_2_traits_2<K>
MinEllipse2Traits

CGAL::min_rectangle_2
CGAL::min_parallelogram_2
CGAL::min_strip_2
CGAL::Min_quadrilateral_default_traits_2<R>
MinQuadrilateralTraits_2

CGAL::rectangular_p_center_2
CGAL::Rectangular_p_center_default_traits_2<R>
RectangularPCenterTraits_2

CGAL::Min_sphere_d<Traits>
CGAL::Min_annulus_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

CGAL::Min_sphere_of_spheres_d<Traits>
MinSphereOfSpheresTraits

Inscribed Areas

CGAL::maximum_area_inscribed_k_gon_2
CGAL::maximum_perimeter_inscribed_k_gon_2
CGAL::extremal_polygon_2
CGAL::Largest_empty_iso_rectangle_2<Traits>
CGAL::Extremal_polygon_area_traits_2<K>
CGAL::Extremal_polygon_perimeter_traits_2<K>
ExtremalPolygonTraits_2
LargestEmptyIsoRectangleTraits_2

Optimal Distances

CGAL::all_furthest_neighbors_2
AllFurthestNeighborsTraits_2

CGAL::Width_3<Traits>
CGAL::Width_default_traits_3<K>
WidthTraits_3

CGAL::Polytope_distance_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

Advanced Techniques

CGAL::monotone_matrix_search
CGAL::Dynamic_matrix<M>
MonotoneMatrixSearchTraits
BasicMatrix

CGAL::sorted_matrix_search
CGAL::Sorted_matrix_search_traits_adaptor<F,M>
SortedMatrixSearchTraits

• Min_circle_2<Traits>

• Min_circle_2_traits_2<K>

• MinCircle2Traits

• Circle

• Min_ellipse_2<Traits>

• Min_ellipse_2_traits_2<K>

• MinEllipse2Traits

• Ellipse

• min_rectangle_2

• min_parallelogram_2

• min_strip_2

• Min_quadrilateral_default_traits_2<Kernel>

• MinQuadrilateralTraits_2

• rectangular_p_center_2

• Rectangular_p_center_default_traits_2<R>

• RectangularPCenterTraits_2

• Min_sphere_d<Traits>

• Min_annulus_d<Traits>

• Min_sphere_of_spheres_d<Traits>

• MinSphereOfSpheresTraits

• Min_sphere_of_spheres_d_traits_2<K,FT,UseSqrt,Algorithm>

• Min_sphere_of_spheres_d_traits_3<K,FT,UseSqrt,Algorithm>

• Min_sphere_of_spheres_d_traits_d<K,FT,Dim,UseSqrt,Algorithm>

• Optimisation_d_traits_2<K,ET,NT>

• Optimisation_d_traits_3<K,ET,NT>

• Optimisation_d_traits_d<K,ET,NT>

• OptimisationDTraits

• maximum_area_inscribed_k_gon_2

• maximum_perimeter_inscribed_k_gon_2

• extremal_polygon_2

• Extremal_polygon_area_traits_2<K>

• Extremal_polygon_perimeter_traits_2<K>

• ExtremalPolygonTraits_2

• Largest_empty_iso_rectangle_2<T>

• LargestEmptyIsoRectangleTraits_2

• all_furthest_neighbors_2

• AllFurthestNeighborsTraits_2

• Width_3<Traits>

• Width_default_traits_3<K>

• WidthTraits_3

• Polytope_distance_d<Traits>

• monotone_matrix_search

• Dynamic_matrix<M>

• MonotoneMatrixSearchTraits

• BasicMatrix

• sorted_matrix_search

• Sorted_matrix_search_traits_adaptor<F,M>

• SortedMatrixSearchTraits