Chapter 52Geometric Optimisation

Bernd Gärtner, Thomas Herrmann, Michael Hoffmann, and Sven Schönherr

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

The optimisation code uses infix OPTIMISATION in the assertions, e.g. defining the compiler flag CGAL_OPTIMISATION_NO_PRECONDITIONS switches precondition checking off, cf. Section .

Bounding Areas and Volumes

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

Optimal Distances

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