Approximate Geometric Query Structures:Quasi-BAR Bounds

Quasi-BAR Bounds

We are now ready to examine closely a sufficient condition for a data structure to guarantee efficient performance on the aforementioned searches. Before we can proceed, we must first discuss a few more basic definitions presented in Dickerson et al. [9].

DEFINITION 26.3 For any region R, the region annulus with radius r, denoted AR,r is the set of all points p ∈ IRd such that p ∈/ R and δ(p, R) < r. A region Rl pierces an annulus AR,r if and only if there exist two points p, q ∈ Rl such that p ∈ R and q ∈/ R ∪ AR,r .

In other words, an annulus AR,r contains all points outside but near the region R. If R were a sphere of radius rl, this would be the standard definition of an annulus with inner radius rl and outer radius rl + r. For convenience, when the region and radius of an annulus are understood, we use A. Figure 26.5 illustrates the basic idea of a spherical annulus with multiple piercing regions.

The core of the performance analysis for the searches lies in a critical packing argument.

The packing lemmas work by bounding the number of disjoint regions that can pierce an annulus and hence simultaneously fit inside the annulus, see Figure 26.5b.

When this packing size is small, the searches are efficient. Rather than cover each structure’s search analysis separately, we use the following more generalized notion from Dickerson et al. [9].

DEFINITION 26.4 Given a BSP tree T and a region annulus A, let P (A) denote the largest set of disjoint nodes in T whose associated regions pierce A. A class of BSP trees is a ρ(n)-quasi-BAR tree if, for any tree T in the class constructed on a set S of n points in IRd and any region annulus AR,r , |P (AR,r )|≤ ρ(n)VA /rd, where VA is the volume of AR,r .

The function ρ(n) is called the packing function.

Basically, the packing function ρ(n) represents the maximum number of regions that can pierce any query annulus. By proving that a class of BSP trees is a ρ(n)-quasi-BAR tree, we can automatically inherit the following theorems proven in [1, 3, 13] and generalized in [9]:

THEOREM 26.1 Suppose we are given a ρ(n)-quasi-BAR tree T with depth DT = Ω(log n) constructed on a set S of n points in IRd. For any query point q, the priority search algorithms in Figures 26.2 and 26.3 find respectively a (1 + E)-nearest and a (1 − E)-farthest neighbor to q in O(E1−dρ(n)DT ) time.

THEOREM 26.2 Suppose we are given a ρ(n)-quasi-BAR tree T with depth DT con- structed on a set S of n points in IRd. For any convex query region Q, the search algorithm in Figure 26.4 solves an E-approximate range searching query in T in O(E1−dρ(n)DT ) time (plus output size in the reporting case). For any general non-convex query region Q, the time required is O(E−dρ(n)DT ) (plus output size).∗

Trivially, ρ(n) is always less than n but this accomplishes little in the means of getting good bounds. Having a class of trees with both a good packing function and low depth helps guarantee good asymptotic performance in answering geometric queries. One approach to finding such classes is to require that all regions produced by the tree be fat. The idea behind this is that there is a limit to the number of disjoint fat regions that pierce an annulus dependent upon the aspect ratio of the regions and the thickness of the annulus. Unfortunately, guaranteeing fat regions and good depth is not readily possible using the standard BSP trees like k-d trees and octrees. Imagine building a k-d tree using only axis-parallel partitioning cuts.

Figure 26.6 illustrates such an example.

Here the majority of the points are concentrated at a particular corner of a rectangular region. Now, any axis-parallel cut is either too close to the opposing face or does not partition the points in the region well, resulting in large tree depth.

Fortunately, there are structures that can provably be shown to be ρ(n)-quasi-BAR trees with small values for ρ(n) and DT . The next few sections discuss some of these structures.

FIGURE 26.6: (a) A bad corner of a simple rectangular region with nearly all of the points clustered near a corner. Notice a cut in either the x or y direction dividing the points located inside p would cause a “skinny” region. (b) The same situation in IR3.