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 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
Previous Page Next Page