TryAlgo

Covering points with a strip

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.

Strip

This leads to the following algorithm.

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.

def left_turn(a, b, c):
return (a[0] - c[0]) * (b[1] - c[1]) - (a[1] - c[1]) * (b[0] - c[0]) > 0

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.

def dist2(p0, p1, p2):
x0, y0 = p0
x1, y1 = p1
x2, y2 = p2
num = ((y2 - y1)*x0 - (x2 - x1)*y0 + x2 * y1 - y2 * x1) ** 2
denom = (y2 - y1)**2 + (x2 - x1)**2
return float(num) / denom

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.

def andrew(S):
S.sort()
top = []
bot = []
for p in S:
while len(top) >= 2 and not left_turn(p, top[-1], top[-2]):
top.pop()
top.append(p)
while len(bot) >= 2 and not left_turn(bot[-2], bot[-1], p):
bot.pop()
bot.append(p)
return bot[:-1] + top[:0:-1]

Further applications

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