Geometric Optimization
Reference Manual

This chapter describes concepts, classes, and functions for solving geometric optimization 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), approximate minimum-volume enclosing ellipsoid with user-specified approximation ratio (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

38.4   Classified References Pages

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::Approximate_min_ellipsoid_d<Traits>
ApproximateMinEllipsoid_d_Traits_d

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<T>
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

38.5   Alphabetical List of Reference Pages

AllFurthestNeighborsTraits_2

all_furthest_neighbors_2

ApproximateMinEllipsoid_d_Traits_d

Approximate_min_ellipsoid_d<Traits>

Approximate_min_ellipsoid_d_traits_2<K,ET>

Approximate_min_ellipsoid_d_traits_3<K,ET>

Approximate_min_ellipsoid_d_traits_d<K,ET>

BasicMatrix

Circle

Dynamic_matrix<M>

Ellipse

ExtremalPolygonTraits_2

extremal_polygon_2

Extremal_polygon_area_traits_2<K>

Extremal_polygon_perimeter_traits_2<K>

LargestEmptyIsoRectangleTraits_2

Largest_empty_iso_rectangle_2<T>

maximum_area_inscribed_k_gon_2

maximum_perimeter_inscribed_k_gon_2

MinCircle2Traits

MinEllipse2Traits

MinQuadrilateralTraits_2

MinSphereOfSpheresTraits

Min_annulus_d<Traits>

Min_circle_2<Traits>

Min_circle_2_traits_2<K>

Min_ellipse_2<Traits>

Min_ellipse_2_traits_2<K>

min_parallelogram_2

Min_quadrilateral_default_traits_2<Kernel>

min_rectangle_2

Min_sphere_d<Traits>

Min_sphere_of_spheres_d<Traits>

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>

min_strip_2

MonotoneMatrixSearchTraits

monotone_matrix_search

OptimisationDTraits

Optimisation_d_traits_2<K,ET,NT>

Optimisation_d_traits_3<K,ET,NT>

Optimisation_d_traits_d<K,ET,NT>

Polytope_distance_d<Traits>

RectangularPCenterTraits_2

rectangular_p_center_2

Rectangular_p_center_default_traits_2<R>

SortedMatrixSearchTraits

Sorted_matrix_search_traits_adaptor<F,M>

sorted_matrix_search

WidthTraits_3

Width_3<Traits>

Width_default_traits_3<K>