Algorithm animation (2/5)

Figure 8

Processing a point p

When the sweep line reaches a point p (i.e. the fourth point in the figure above), we must determine if p forms a new closest pair with another point to the left of the sweep line. We do not need to examine all points to the left of the sweep line but only those which are sufficiently close to p. This means that we only check the points which lie in the depicted half circle around p. The radius of the half circle is the distance of the closest pair found so far. If this half circle is empty, as in the figure above, we continue without changing the closest pair. We proceed in the animation by clicking the Continue button.

Up Left Start of sample run End of sample run Right