Rotating Calipers: thinnest strip transversals

Thinnest strip transversals

Consider the following facility location problem: A set of "customers" is given as a family F of convex polygons on the plane. The goal is to find the "facility", a line on the plane, minimizing the maximum distance from the line to any customer.

This last point needs some clarification. The distance from the line to any polygon is the minimum orthogonal distance from the line to any point on that polygon. Therefore, each polygon has a unique distance to the line.
Now, given the family of polygons and a line on the plane, each polygon has a distance to the line. Therefore, a maximum line-polygon distance exists for the entire family. This distance depends on the line as well as the family of polygons.
The goal of the problem is: given a specific family of polygons, find the line that minimizes this maximum. Other versions of the problem exist, notably that of finding the line minimizing the sum of distances, and the sum of weighted distances to the polygons.

The results presented here are due to Robert and Toussaint (1990).
The main problem is equivalent to finding the minimum width strip (a region on the plane bounded by two parallel lines) intersecting all polygons of the family. Then, the medial axis of that strip (the line parallel and equidistant to the strip's boundaries) is the desired line minimizing the maximum distance.

The following definitions are necessary for the discussion of the main result:

A line l on the plane, defined by the equation ax+by+c=0 (with b > 0 or a=-1) divides the plane into two regions: the upper half Hu(l) of points p=(px,py) such that apx + apy + c >= 0 and the lower half Hl(l) of points p=(px,py) such that apx + apy + c <= 0.
By this definition, if the line is vertical, the upper half contains negative infinity of the x axis.

Furthermore, a strip can be defined as the intersection of the upper-half of one line, with the lower-half of another (parallel) line.

Given a convex polygon P, and an orientation theta, the lower tangent line tl(P, theta) is a line having angle theta with respect to the positive x axis, intersecting P and such that P belongs to the upper-half of tl(P, theta). The intersection point (or points) is called the lower point.
Similarly, the upper tangent and upper point are defined.
Given a family of polygons and a fixed orientation, a set of lower points and upper points is determined.

Finally, consider the following result:
Given a family F of polygons, and an orientation theta , a strip S (given by the intersection of Hu(l1) with Hl(l2) of width greater than 0 is the minimum width strip for F (at that orientation) if, and only if there exist two polygons P and Q belonging to F such that

The intersection of P and Hu(l1) is in l1.
The intersection of Q and Hl(l2) is in l2.

The main result follows from this: the minimum width strip (with a given orientation theta) for a family F of convex polygons is determined by lines l1 and l2 such that
l1=tl(CH(UP(F, theta)), theta) and
l2=tu(CH(LP(F, theta)), theta)
Illustrating the main result

A family of convex polygons, and the minimum width strip for a given orientaiton. The convex hulls of lower and upper half points are shown, illustrating the above result. Note the existence of the two polygons intersecting the strip only at one vertex.

Therefore, if one can determine the sequence of lower and upper points for the family's polygons, computing the convex hulls for a given direction determine the minimum width-strip. As Robert and Toussaint explain, luckily these convex hulls need not be completely recomputed each time: they need only be updated. Indeed, consider two close orientations: it is likely for many (or all) polygons to have the same upper and lower points for these two orientations. This fact also implies that only a critical number of orientations (when a lower or upper point changes) need to be checked.

As the focus here is on the Rotating Calipers paradigm, it is not the purpose to go into the details of the algorithm. The authors propose the use of the Rotating Calipers to compute upper and lower points for the polygons. The following is the outline of an algorithm accomplishing just that. Given a convex polygon P:

Find the vertices with minimum and maximum y-coordinates. Label these as p and q and construct horizontal lines of support through them.
Rotate the lines counterclockwise by an angle theta until one is flush with one of the polygon's edges.
If the vertex hit was the vertex after p (given a counterclockwise order), then p is the lower point for orientations 0 (inclusive) to theta (non-inclusive). If it is the vertex after q, then q is the upper point for the same angle interval. Possibly both these cases occur if edges are parallel.
Update the current points to the new vertex of vertices hit, and the current angle.
Repeat steps 2 to 4, updating the angle intervals accordingly, until the new current angle is at least 180 degrees (at which point the lines return to their original positions, but in reverse order).

The directions at which a line is flush with one of the polygon's edges are called critical directions. It is only. at these orientations that lower or upper points can change. At a critical direction, since the line intersects two vertices, the lower or upper point is defined as the one intersecting the line if it is rotated counterclockwise.

Once the critical directions (given in order) are known, a strip can be computed for the first direction. Then, for the second critical direction, at least one lower or upper point is updated. Because of this, the convex hulls need only be updated, and not recomputed. Once this is done, the new strip is obtained, and its width (the orthogonal distance between its boundaries) computed. This process is repeated for all critical directions. Note that if at any point in the process a strip f width 0 is found, then the process can be stopped because a line is found that intersects all polygons of the family.

For the complete algorithm, discussion of the correctness and the running time, consult the authors' paper:

J.-M. Robert, G.T. Toussaint. Computational geometry and facility location. Proc. Internatioanl Conf. on Operations Research and Management Science, Manila, The Philippines, Dec. 11-15, 1990. pp B-1 to B-19.

December 17th, 1998