Geometric Optimisation

Geometric optimisation deals with problems of computing geometric
objects which are optimal subject to certain criteria and constraints.
Our running example will be the problem of computing the sphere of
smallest radius which contains a given point set in $$*d*-dimensional
Euclidean space.

The geometric optimisation algorithms in CGAL fall into three categories, ``Bounding Volumes'', ``Optimal Distances'' and ``Advanced Techniques''.

This category contains algorithms which for a given point set compute
the ``best'' circumscribing (or inscribed) object from a specific
class. If the class consists of all spheres in $$*d*-dimensional
Euclidean space and ``best'' is defined as having smallest radius,
then we obtain the smallest enclosing sphere problem already mentioned
above.

In the following example a smallest enclosing circle
(*CGAL::Min_circle_2<Traits>*) is constructed from points
on a line and written to standard output. The example
shows that it is advisable to switch on random shuffling
in order to deal with a `bad' order of the input points.

#include <CGAL/Homogeneous.h> #include <CGAL/Min_circle_2.h> #include <CGAL/Min_circle_2_traits_2.h> #include <CGAL/Gmpz.h> #include <iostream> // typedefs typedef CGAL::Gmpz NT; typedef CGAL::Homogeneous<NT> K; typedef CGAL::Min_circle_2_traits_2<K> Traits; typedef CGAL::Min_circle_2<Traits> Min_circle; typedef K::Point_2 Point; // main int main( int, char**) { int n = 100; Point* P = new Point[ n]; for ( int i = 0; i < n; ++i) P[ i] = Point( (i%2 == 0 ? i : -i), 0); // (0,0), (-1,0), (2,0), (-3,0), ... Min_circle mc1( P, P+n, false); // very slow Min_circle mc2( P, P+n, true); // fast CGAL::set_pretty_mode( std::cout); std::cout << mc2; delete[] P; return( 0); }

Other classes for which we provide solutions are ellipses
(*CGAL::Min_ellipse_2<Traits>*), rectangles (*CGAL::min_rectangle_2*),
parallelograms (*CGAL::min_parallelogram_2*) and strips
(*CGAL::min_strip_2*) in the plane, with appropriate optimality
criteria. In addition to spheres for points
(*CGAL::Min_sphere_d<Traits>*) and spheres for spheres
(*CGAL::Min_sphere_of_spheres_d<Traits>*), there
is another class of objects which allows for solutions in arbitrary
dimension, namely annuli (*CGAL::Min_annulus_d<Traits>*).

Bounding volumes can be used to obtain simple approximations of complicated objects. For example, consider the problem of deciding whether two moving polygons currently intersect. An obvious solution is to discretize time and perform a full intersection test for any time step. If the polygons are far apart most of the time, this is unnecessary. Instead, simple bounding volumes (for examples, circles) are computed for both polygons at their initial positions. At subsequent time steps, an intersection test between the moving bounding circles replaces the actual intersection test; only if the circles do intersect, the expensive intersection test between the polygons is performed. In practice, bounding volume hierarchies are often used on top of simple bounding volumes to approximate complicated objects more accurately.

As far as inscribed volumes are concerned, we provide algorithms for
computing maximal inscribed $$*k*-gons (triangles, quadrilaterals,
...) of a planar point set $$*P*. Maximal $$*k*-gons are convex, and it
is known that their vertices can be chosen to be vertices of the
convex hull of $$*P*. Hence, the functions
*CGAL::maximum_area_inscribed_k_gon_2* and
*CGAL::maximum_perimeter_inscribed_k_gon_2* operate on convex polygons
only. The example below shows that the largest area triangle (green)
and the largest perimeter triangle (orange, containing the top point)
of a point set are different in general.

We further provide an algorithm for computing the maximal area inscribed axis parallel rectangle

Given a set of points in the plane, the class *CGAL::Largest_empty_iso_rectangle_2<T>*
is a data structure that maintains an iso-rectangle with the largest area among
all iso-rectangles that are inside a given iso-rectangles, and
that do not contain any point of the point set.

Bounding and inscribed volumes are also frequently applied to extract geometric properties of objects. For example, the smallest enclosing annulus of a point set can be used to test whether a set of points is approximately cospherical. Here, the width of the annulus (or its area, or still another criterion that we use) is a good measure for this property. The largest area triangle is for example used in heuristics for matching archaeological aerial photographs. Largest perimeter triangles are used in scoring cross country soaring flights, where the goal is basically to fly as far as possible, but still return to the departure airfield. To score simply based on the total distance flown is not a good measure, since circling in thermals allows to increase it easily.

Bounding volumes also define geometric ``center points'' of objects.
For example, if two objects are to be matched (approximately), one
approch is to first apply the translation that maps the centers of
their smallest enclosing spheres onto each other. Simpler centers are
possible, of course (center of gravity, center of bounding box), but
more advanced bounding volumes might give better results in some
cases. It can also make sense to consider several center points
instead of just one. For example, we provide algorithms to cover a
planar point set with between two and four minimal boxes
(*CGAL::rectangular_p_center_2*). Below is an example covering with
three boxes; the center points are shown in red.

To avoid later disappointment: one very nice class of bounding volumes, namely ellipsoids in three- and higherdimensional space, is currently not supported by CGAL. The reason is that the algebraic complexity of this problem is still beyond the level which would allow us to come up with a solution that satisfies the CGAL standards. We are working on a solution for 3-space, though.

This section currently consists of two algorithms only. On one hand,
one can compute the computation of the distance between the convex
hulls of two given point sets in $$*d*-dimensional Euclidean space
(*CGAL::Polytope_distance_d<Traits>*). Moreover, it is possible to
compute the width of a point set in three dimensions
(*CGAL::Width_3<Traits>*).

The obvious application is collision detection between convex bodies in space. In the spirit of the bounding volume application above, it also makes sense for nonconvex objects: a full intersection test between complicated objects could in a first stage be approximated with the test between the convex hulls of the objects. Only if the hulls intersect, a full intersection test is necessary.

To dampen fears concerning the performance of the distance
computation, we want to mention that the convex hulls of the input
point sets are not explicitly computed. This avoids a runtime which
grows exponentially in $$*d*. In fact, the runtime is almost always
linear in the size of the two point sets.

Geometric optimisation is a well-studied subject also in theory. Consequently, general design principles have been developed from which solutions to diverse problems arise. For example, although the problems of computing the smallest enclosing sphere of a point set and the problem of computing the distance between two convex hulls seem to be quite different, they are both instances of a more general optimisation problem, named ``quadratic programming''. To be more specific, CGAL's solutions for the two quadratic programming instances just mentioned are based on a general quadratic programming solver, which will be documented as a separate unit in future releases.

Two techniques that we make available in this section are
*CGAL::monotone_matrix_search* and *CGAL::sorted_matrix_search*. They deal
with the problem of efficiently finding largest entries in matrices
with certain structural properties. Many concrete problems can be
modelled as matrix search problems, and for some of them we provide
explicit solutions that allow you to solve them without knowing about
the matrix search technique. Examples are, the computation of all
furthest neighbors for the vertices of a convex polygon, maximal
$$*k*-gons inscribed into a planar point set, and computing rectangular
$$*p*-centers.

Next chapter: Geometric Optimisation

The CGAL Project .
Tue, December 21, 2004 .