than a certain number of points has been inserted afterwards. We want to point out that there

are certain applications for which a point-by-point insertion is necessary, for example, if

greedy methods for solving partial differential equations numerically are employed. But,

as said before, we will concentrate in the following on the most important case, where all

points are given in advance.

230

14.1 The ¬xed-grid method 231

Here, then, are the queries that the data structure should at least be able to answer

ef¬ciently.

r Nearest neighbor search Given a point x ∈ , what is the nearest neighbor of x from X ? The

nearest neighbor is de¬ned to be the point from X that has minimal distance to x among all points

from X . Of course, the nearest neighbor does not need to be unique.

r nearest neighbors search More generally, given a point x ∈ and a number ∈ N, what are

the nearest neighbors of x from X ?

r Range search Given a region R, what are the points X © R? We have to answer this question in

particular in the situation where R is a rectangle or a ball. In this situation we can hope for better

results than in general.

While a range search has already appeared in the context of the moving least squares

approximation, the nearest-neighbor problem comes into play naturally if we want to com-

pute the separation distance q X for a given data set. If it is possible to compute the nearest

neighbor of a point x in constant time then we can compute q X in O(N ), which is favor-

ably cheap when compared with the naive approach of computing all distances x j ’ xk 2

having O(N 2 ) complexity.

Some algorithms introduced in the next chapter cover the region by a ¬nite number

of overlapping regions j , i.e. = ∪ M j=1 j such that every point x ∈ is contained in at

most K > 0 regions j . Here, K > 0 is an integer independent of x but depending on and

on the covering { j }. This is a kind of a dual problem to the problems we have encountered

so far. Thus we need a data structure that is able to solve the problem, as follows.

r Containment query Given x ∈ such that x ∈

report all regions j.

j

Before we start looking at speci¬c data structures let us discuss the brute force method. The

naive approach would simply store the points X in an N -dimensional array of d-dimensional

vectors and try to manage with that. Obviously, this would need O(d N ) space and O(d N )

time to built the “data structure”; these are the minimum necessary. Unfortunately, it is also

obvious that a nearest-neighbor query can only be answered by testing all points in X , which

costs O(N ) time. The same is true for range search and containment query; both have an

O(N ) complexity in time. We have already seen in the context of moving least squares that

this is unacceptable.

14.1 The ¬xed-grid method

Our ¬rst data structure is based on the simple idea of covering the region by disjoint

cubes of equal side length. For every cube we list the indices of the centers contained in

it. It turns out that this method is very ef¬cient for quasi-uniform data sets. Before we go

more into details let us review some important properties of quasi-uniform data sets.

Let ⊆ Rd be bounded. Fix a quasi-uniformity constant cqu > 0. Then we say that a set

of pairwise distinct centers X = {x1 , . . . , x N } ⊆ is quasi-uniform with respect to cqu if

q X ¤ h X, ¤ cqu q X ,

232 Data structures

where q X and h X, are the usual separation and ¬ll distance, respectively. To require q X ¤

h X, instead of c1 q X ¤ h X, is not a restriction if satis¬es an interior cone condition

with radius r > 0. If q X ¤ r we can ¬nd for an x1 ∈ X a point y ∈ with y ’ x1 2 = q X .

Hence

y ’ xj ≥ x j ’ x1 ’ x1 ’ y ≥ 2q X ’ q X = q X

2 2 2

for any other x j ∈ X . But this means that h X, ≥ q X .

The nice thing about quasi-uniform sets is that not only are q X and h X, equivalent in

the sense that their fractions can be bounded from above and below by constants but also

both are equivalent to N ’1/d .

⊆ Rd be bounded and measurable. Suppose that X =

Proposition 14.1 Let

{x1 , . . . , x N } ⊆ is quasi-uniform with respect to cqu > 0. Then there exist constants

c1 , c2 > 0 depending only on the space dimension d, on , and on cqu such that

c1 N ’1/d ¤ h X, ¤ c2 N ’1/d .

Proof By de¬nition of h = h X, we have

N

⊆ B(x j , h),

j=1

hence a comparison of the volumes gives

π d/2

vol( ) ¤ N h d

(d/2 + 1)

or h ≥ c1 N ’1/d . For the second inequality note that since is bounded there exists a ball

B(x0 , R) with ⊆ B(x0 , R). Thus we have

N

B(x j , q X ) ⊆ B(x0 , R + q X ).

j=1

The balls B(x j , q X ) are essentially disjoint by de¬nition of q X . Hence N q X ¤ (R + q X )d or

d

’d

N ¤ (1 + R/q X )d ¤ (2R)d q X , if q X ¤ R. Note that q X > R does not make sense because

in that situation X consists only of one point. The quasi-uniformity of X now leads to

N ¤ (2Rcqu )d h ’d , showing also that h ¤ c2 N ’1/d .

Obviously, the equivalence of q X and h X, and the equivalence of h X, and N ’1/d lead

to the equivalence of q X and N ’1/d . The next result is similar to a result that we achieved

for moving least squares.

Corollary 14.2 Suppose that X = {x1 , . . . , x N } ⊆ is quasi-uniform. For any cube W =

W (y, cs N ’1/d ) of side length 2cs N ’1/d the number of centers in X © W is bounded by a

constant that is independent of N .

14.1 The ¬xed-grid method 233

Proof We argue as in the second part of the proof of Proposition 14.1. Let Y =

{y1 , . . . y M } = X © W . Then the inclusion

√

M

dcs N ’1/d + q X ) ⊆ B(y, cq X )

B(y j , q X ) ⊆ B(y,

j=1

shows that M ¤ cd , where c depends only on cqu , , d.

Let us come back to the initial problem of de¬ning a good data structure. The ¬rst step is

to ¬nd the bounding box for . In many applications is not known in advance. Moreover,

building the data structure is a problem relating just to the point set X and not to . Hence,

we will look for the bounding box B B for X instead . Let us denote the coordinates of

the points by x j = (x j,1 , . . . , x j,d )T .

Algorithm 1 Building the grid structure

Data sites x1 , . . . , x N ∈ Rd .

Input:

Output: For each grid cell a list of those points contained in it.

Find the bounding box B B for the data points.

De¬ne a grid consisting of N 1/d d equally sized cells on Q.

for every grid cell do

Initialize a list of indices for the points contained in that cell.

for 1 ¤ j ¤ N do

Determine the cell C with x j ∈ C.

Store j in the list for cell C.

Algorithm 1 describes how the grid structure can be built. The most dif¬cult part is to

organize the indices for the grid. This can be done in the following way. Choose a small

> 0 and let

±k := min x j,k ’ βk := max x j,k

and

1¤ j¤N 1¤ j¤N