Proximity: Fundamental Algorithms

In Chapter 4 we illustrated anO(NlogN)algorithm for finding the two farthest points of a plane set. One may think that finding the two closest points would be a simple extension, but it is not. The two farthest points are necessarily hull vertices and we may exploit convexity to give a fast algorithm; the two closest points do not necessarily bear any relation to the convex hull, so a new technique must be developed, which is the subject of this chapter. We will be concerned with a large class of problems that involve the proximity of points in the plane and our goal will be to deal with all of these seemingly unrelated tasks via a single algorithm, one that discovers, processes, and stores compactly all of the relevant proximity information. To do this, we revive a classical mathematical object, the Voronoi diagram, and turn it into an efficient computational structure that permits vast improvement over the best previously known algorithms. In this chapter, several of the geometric tools we have discussed earlier—such as hull-finding and searching—will be used to attack this large and difficult class—theclosest-pointorproximity problems.