# Résolution de problèmes algorithmiques

Given n points in the 2-dimensional plane find a strip with minimal width that covers all the points.

## Convex hull

The key observation is that a narrowest strip touches at least 2 successive points a, b on the convex hull on one side of the strip and a point c on the convex hull on the opposite side.

This leads to the following algorithm.

• Compute the convex hull of the points, and restrict to these points.
• Loop over every pair of successive points a, b on the hull, and maintain a point c that is furthest to the line a-b.
• Return the smallest observed point-to-line distance.

The first step takes time $O(n\log n)$, while the second step takes time $O(n)$.

## Implementation

In computational geometry problems you want to avoid the use of trigonometric functions, and do all the computations if possible using only integer additions and multiplications. Just two computational geometry tools are necessary to solve the above problem. One is to determine the orientation of a point c with respect to the directed line defined by two points a and b.

And the second needed tool is the computation of the squared distance between a point p0 and a line defined by points p1 and p2. Squaring the distance is a trick that enables to stay within integer computations and even saves some computational time.

## Convex hull

For the convex hull you can use Grahams algorithm or Andrew. Personally I prefer the last one, but they are not much different.

## Further applications

This algorithm is called Rotating calipers and can be used to solve various related problems, such as for example:

• finding the furthest pair of points of a given set,
• compute the diameter of a convex polygon,
• compute the distance between two polygons,
• compute the smallest rectangular bounding box for a set of rectangles.