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