Two-dimensional example problem
Given a set of points, the two-dimensional example problem is a more sophisticated example where we seek for the smallest disc containing all the given points. The problem is formulated as two-dimensional minimization problem which is solved by the use of interval arithmetic.
Facility location problems
The Weber problem
The two-dimensional Weber problem is to find a location for a new facility on the plane which minimizes the weighted sum of Euclidean distances to a given set of demand points. If some weights are positive and others are negative, global optimization techniques lead to helpful solution algorithms.
The median circle problem
The median circle problem is to locate a circle so as to minimize the sum of distances between the circumference and some given demand points on the plane. Since every circle can be defined by its center and radius, we have a three-dimensional problem.
The 2-median problem
The 2-median problem is to find two new facilities on the Euclidean plane taking some given demand points into account. Hence, we are dealing with a four-dimensional problem.
The 3-median problem
The 3-median problem is to find three new facilities on the Euclidean plane taking some given demand points into account. Hence, we are dealing with a six-dimensional problem such the run-times of the geometric branch-and-bound algorithm increases significantly compared to the 2-median problem.
The circle detection problem
The circle detection problem is to find an imperfect pictured circle in a set of two-dimensional points. This problem is well known in image processing where the set of points is derived from an image applying an edge detection algorithm. Note that in the same manner it is also possible to detect other shapes such as lines or ellipses.
The rigid transformation problem
The two-dimensional rigid transformation problem is to align two sets of points in the Euclidean space for which correspondence is known. The transformation is defined by a rotation matrix and a translation vector such that we obtain a three-dimensional optimization problem.