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