2 1. THE POWER OF GRIDS – CLOSEST PAIR AND SMALLEST ENCLOSING DISK Problem 1.4. Given a set P of n points in the plane, find the pair of points closest to each other. Formally, return the pair of points realizing CP(P) = min p q, p,q∈P p − q . The following is an easy standard packing argument that underlines, under various disguises, many algorithms in computational geometry. α p Lemma 1.5. Let P be a set of points contained inside a square , such that the sidelength of is CP(P). Then |P| ≤ 4. Proof. Partition P into four equal squares 1 ,..., 4 , and observe that each of these squares has diameter √ 2α/2 α, and as such each can contain at most one point of P that is, the disk of radius α centered at a point p ∈ P completely covers the subsquare containing it see the figure on the right. Note that the set P can have four points if it is the four corners of . Lemma 1.6. Given a set P of n points in the plane and a distance α, one can verify in linear time whether CP(P) α, CP(P) = α,or CP(P) α. Proof. Indeed, store the points of P in the grid Gα. For every non-empty grid cell, we maintain a linked list of the points inside it. Thus, adding a new point p takes constant time. Specifically, compute id(p), check if id(p) already appears in the hash table, if not, create a new linked list for the cell with this ID number, and store p in it. If a linked list already exists for id(p), just add p to it. This takes O(n) time overall. Now, if any grid cell in Gα(P) contains more than, say, 4 points of P, then it must be that the CP(P) α, by Lemma 1.5. D p α Thus, when we insert a point p, we can fetch all the points of P that were already inserted in the cell of p and the 8 adjacent cells (i.e., all the points stored in the cluster of p) that is, these are the cells of the grid Gα that intersects the disk D = disk(p,α) centered at p with radius α see the figure on the right. If there is a point closer to p than α that was already inserted, then it must be stored in one of these 9 cells (since it must be inside D). Now, each one of those cells must con- tain at most 4 points of P by Lemma 1.5 (oth- erwise, we would already have stopped since the CP(·) of the inserted points is smaller than α). Let S be the set of all those points, and observe that |S| ≤ 9 · 4 = O(1). Thus, we can compute, by brute force, the closest point to p in S . This takes O(1) time. If d(p, S ) α, we stop otherwise, we continue to the next point. Overall, this takes at most linear time. As for correctness, observe that the algorithm returns ‘CP(P) α’ only after finding a pair of points of P with distance smaller than α. So, assume that p and q are the pair of points of P realizing the closest pair and that p − q = CP(P) α. Clearly, when the later point (say p) is being inserted, the set S would contain q, and as such the algorithm would

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2011 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.