CHAPTER 1 The Power of Grids – Closest Pair and Smallest Enclosing Disk In this chapter, we are going to discuss two basic geometric algorithms. The first one computes the closest pair among a set of n points in linear time. This is a beautiful and surprising result that exposes the computational power of using grids for geometric com- putation. Next, we discuss a simple algorithm for approximating the smallest enclosing ball that contains k points of the input. This at first looks like a bizarre problem but turns out to be a key ingredient to our later discussion. 1.1. Preliminaries For a real positive number α and a point p = (x, y) in IR2, define Gα(p) to be the grid point ( x/α α, y/α α). We call α the width or sidelength of the grid Gα. Observe that Gα partitions the plane into square regions, which we call grid cells. Formally, for any i, j ∈ Z, the intersection of the halfplanes x ≥ αi, x α(i + 1), y ≥ αj, and y α(j + 1) is said to be a grid cell. Further we define a grid cluster as a block of 3 × 3 contiguous grid cells. Note that every grid cell of Gα has a unique ID indeed, let p = (x, y) be any point in , and consider the pair of integer numbers id = id(p) = ( x/α , y/α ). Clearly, only points inside are going to be mapped to id . We can use this to store a set P of points inside a grid eﬃciently. Indeed, given a point p, compute its id(p). We associate with each unique id a data-structure (e.g., a linked list) that stores all the points of P falling into this grid cell (of course, we do not maintain such data-structures for grid cells which are empty). So, once we have computed id(p), we fetch the data-structure associated with this cell by using hashing. Namely, we store pointers to all those data-structures in a hash table, where each such data-structure is indexed by its unique id. Since the ids are integer numbers, we can do the hashing in constant time. Assumption 1.1. Throughout the discourse, we assume that every hashing operation takes (worst case) constant time. This is quite a reasonable assumption when true randomness is available (using for example perfect hashing [CLRS01]). Assumption 1.2. Our computation model is the unit cost RAM model, where every opera- tion on real numbers takes constant time, including log and · operations. We will (mostly) ignore numerical issues and assume exact computation. Definition 1.3. For a point set P and a parameter α, the partition of P into subsets by the grid Gα is denoted by Gα(P). More formally, two points p, q ∈ P belong to the same set in the partition Gα(P) if both points are being mapped to the same grid point or equivalently belong to the same grid cell that is, id(p) = id(q). 1.2. Closest pair We are interested in solving the following problem: 1 http://dx.doi.org/10.1090/surv/173/01

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.