Approximate Geometric Query Structures:BAR Trees

BAR Trees

The balanced aspect ratio tree introduced in [12] for the basic two-dimensional case and subsequently revised to higher dimensions in [11, 13] can be shown to have a packing function of ρ(n) = O(1) where the constant factor depends on the dimension d and a user-specified aspect ratio parameter α. In the following section, we borrow terminology from [11, 13].

Unlike BBD trees, k-d trees, and octrees, BAR trees do not exclusively use axis-orthogonal hyperplane cuts. Instead, to achieve simultaneously the goals of good aspect ratio, balanced depth, and convex regions, cuts in several different directions are used. These directions are called canonical cuts, and the particular choice and size of canonical cuts is essential in creating good BAR trees.

DEFINITION 26.5 The following terms relate to specific cutting directions:

Figure 26.8a shows a region composed of three cut directions (1, 0), (0, 1), and (1, −1), or simply cuts along the x, y, and x − y directions. After cutting the region at the dashed line c, we have two regions R1 and R2. In R2 notice the left side is replaced by the new cut c, and more importantly the diagonal cut is no longer tangential to R2. The following definition describes this property more specifically.

DEFINITION 26.6 A canonical cut c defines a canonical region R, written c ∈ R, if and only if c is tangential to R. In other words, c intersects the border of R. For a canonical region R, any two parallel canonical cuts b, c ∈ R are opposing canonical cuts. For any canonical region R, we define the canonical bounding cuts with respect to a direction --vi ∈C to be the two unique opposing canonical cuts normal to --vi and tangent to R. We often

FIGURE 26.8: (a) An example of a canonical region of three cut directions, x,y, and x − y. Observe the three widths highlighted with lines and the min and max widths of the region. The left facet associated with the x direction is drawn in bold. The bold dashed line in the center represents a cut c and the respective subregions R1 and R2. (b) An example of a similar region highlighting the two shield regions associated with the x-direction for α ≈ 4.

Notice the size difference between the two shield regions corresponding to the associated facet sizes.

refer to these cuts as bi and ci or simply b and c when i is understood from the context. Intuitively, R is “sandwiched” between bi and ci. To avoid confusion, when referring to a canonical cut of a region R, we always mean a canonical bounding cut.

For any canonical bounding cut, c, the facet of c ∈ R, facetc(R), is defined as the region formed by the intersection of R with c.

The canonical set used to define a partition tree can vary from method to method. For example, the standard k-d tree algorithm [4] uses a canonical set composed of all axis- orthogonal directions.

DEFINITION 26.7 For a canonical set C and a canonical region R, we define the following terms (see Figure 26.8a):

When using a canonical cut ci to partition a region R into two pieces R1 and R2 as the cut gets closer to a side of R, one of the two respective regions gets increasingly skinnier.

At some point, the region is no longer α-balanced, see Figure 26.8b. This threshold region is referred to as a shield region and is defined in [11] as the following:

DEFINITION 26.8 Given an α-balanced canonical region R and a canonical cut di- rection --vi, sweep a cut cl from the opposing cut bi toward ci. Let P be the region of R between cl and ci. Sweep cl until either region P is empty or just before asp(P ) > α. If P

is not empty, then P has maximum aspect ratio. Call the region P the shield region of ci in R, shieldci (R). Let the maximal outer shield, mosi(R), be the shield region shieldbi (R) or shieldci (R) such that |mosi(R)| = max(|shieldbi (R)|, |shieldci (R)|), i.e., the maximal outer shield is the shield region with the greater number of points.

DEFINITION 26.9 An α-balanced canonical region, R, is one-cuttable with reduction factor β, where 1/2 ≤ β < 1, if there exists a cut c1 ∈ C, called a one-cut, dividing R into two subregions R1 and R2 such that the following conditions hold:

1. R1 and R2 are α-balanced canonical regions, 2. |R1|≤ β|R| and |R2|≤ β|R|.

DEFINITION 26.10 An α-balanced canonical region, R, is k-cuttable with reduction factor β, for k > 1, if there exists a cut ck ∈ C, called a k-cut, dividing R into two subregions R1 and R2 such that the following conditions hold:

In other words, the sequence of cuts, ck , ck−1,..., c1, results in k +1 α-balanced canonical regions each containing no more than β|R| points. If the reduction factor β is understood, we simply say R is k-cuttable.

DEFINITION 26.11 For a canonical cut set, C, a binary space partition tree T con- structed on a set S is a BAR tree with maximum aspect ratio α if every region R ∈ T is α-balanced.

Figure 26.9 illustrates an algorithm to construct a BAR tree from a sequence of k-cuttable regions.

THEOREM 26.4 For a canonical cut set, C, if every possible α-balanced canonical region is k-cuttable with reduction factor β, then a BAR tree with maximum aspect ratio α can be constructed with depth O(k log1/β n), for any set S of n points in IRd.

The main challenge in creating a specific instance of a BAR tree is in defining a canonical set C such that every possible α-balanced canonical region is k-cuttable with reduction factor β for reasonable choices of α, β, and k. The α-balanced regions produced help BAR trees have the following packing function.

THEOREM 26.5 For a canonical cut set, C, if every possible α-balanced canonical region is k-cuttable with reduction factor β, then the class of BAR trees with maximum aspect ratio α has a packing function ρ(n) = O(αd ) where the hidden constant factor depends on the angles between the various cut directions. For fixed α, this is constant.

Theorems 26.4 and 26.5 immediately show us that approximate geometric nearest-neighbor and farthest-neighbor queries can be solved in O(E1−d log n) time and approximate geomet- ric range searches for convex and non-convex regions take, respectively, O(E1−d log n) and O(E−d log n) plus the output size. As with the BBD tree, in fact, these structures can also be shown to have running times of O(log n + E1−d log 1 ) for nearest-neighbor and farthest- neighbor queries [11] and O(log n + E1−d) and O(log n + E−d) for convex and non-convex range queries [3].

Another examination of Figure 26.6 shows why simple axis-orthogonal cuts cannot guar- antee k-cuttability. By concentrating a large number of points at an actual corner of the rectangular region, no sequence of axis-orthogonal cuts will divide the points and maintain balanced aspect ratio regions. We can further extend this notion of a bad corner to a general κ-corner associated with a canonical region R.

DEFINITION 26.12 For a canonical cut set C and a canonical region R, a κ-corner B ∈ R is a ball with center ρ and radius κ such that, for every cut direction --vi ∈ C with bounding cuts bi and ci, either bi or ci intersects B, i.e. min(δ(ρ, bi), δ(ρ, ci)) ≤ κ.

When κ = 0, we are not only defining a vertex of a region but a vertex which is tangential to one of every cut direction’s bounding planes. As described in [11], these corners represent the worst-case placement of points in the region. These corners can always exist in regions. However, if one of the facets associated with this corner has size proportional to (or smaller than) the κ ball, then we can still get close enough to this facet and properly divide the point set without introducing unbalanced regions. The following property formalizes this notion more:

Property 26.13 A canonical cut set C satisfies the κ-Corner Property if for any κ ≥ 0 and any canonical region R containing a κ-corner B ∈ R, there exists a canonical cut c ∈ R intersecting B such that lenc(R) ≤ Fκκ for some constant Fκ.

In particular, notice that if κ = 0, one of the bounding cutting planes must intersect at a single point. The advantage to this can be seen in the two-dimensional case. Construct any canonical region using any three cutting directions, for simplicity use the two axis- orthogonal cuts and one cut with slope +1. It is impossible to find a κ-corner without having at least one of the three bounding sides be small with respect to the corner. This small side has a matching very small shield region. Unfortunately, having a small shield region does not mean that the initial region is one-cuttable. The points may all still be concentrated within this small shield region. However, it is possible that this small shield region is one-cuttable. In fact, in [11], it is shown that there exist canonical cut sets that guarantee two-cuttability for sufficient values of α, β, and σ, where the σ parameter is used in the construction. The sufficiency requirements depend only on certain constant properties associated with the angles of the canonical cut set labeled here as Fmin, Fmax, Fbox, and Fκ.

For specific values of these constants, see [11]. Figure 26.10 describes an algorithm to find an appropriate cut.

The general idea is to find the smallest (in physical size) shield region containing am ajority of the points. If none exist, the region must be one-cuttable. Otherwise, we take this shield region and pull the partitioning cut back slightly,† increasing the size of this particular shield region. Given an appropriate cut set and various constant bounds, we can guarantee that this new region is one-cuttable. The following theorems summarize this result [11]:

THEOREM 26.6 (Two-Cuttable Theorem) Suppose we are given a canonical cut set, C, which satisfies the κ-Corner Property 26.13. Any α-balanced canonical region R is

two-cuttable if the following three conditions are met:

THEOREM 26.7 Suppose we are given a canonical cut set C that satisfies the κ-Corner Property and an α > f (C). A BAR tree with depth O(d log n) and balancing factor α can be constructed in O(g(C)dn log n) time, where f and g are constant functions depending on properties of the canonical set. In particular, the running time of the algorithm is O(n log n) for fixed dimensions and fixed canonical sets.

Let us now present two cut sets that do satisfy the κ-Corner Property. The two cut sets we present below are composed of axis-orthogonal cuts and one other set of cuts. Let us give specific names to a few vector directions.

DEFINITION 26.14 A vector v = (x0, x1, x2,..., xd) is

The Corner Cut Canonical Set Cc is the set of all axis-orthogonal cuts and corner cuts. The Wedge Cut Canonical Set Cw is the set of all axis-orthogonal cuts and wedge cuts.

Notice that |Cc| is Θ(2d) and |Cw | is Θ(d2). Although the corner cut canonical set does not necessarily have to be as large as this, the complexity of the corner cut itself means sidedness tests take longer than axis-orthogonal and wedge cuts, namely d computations instead of 1 or 2. The above two canonical sets satisfy the κ-Corner Property 26.13 and from Theorem 26.7, we get the following two corollaries [11]:

COROLLARY 26.1 For the Corner Cut Canonical set Cc, a BAR tree with depth O(d log n) and balancing factor α = Ω(d2) can be constructed in O(n log n) time.

COROLLARY 26.2 For the Wedge Cut Canonical set Cw , a BAR tree with depthO( d log n) and balancing factor α = Ω( d) can be constructed in O(n log n) time.

To get the exact values needed, see [11].

However, it is important to note that the α bounds above are overestimates of the minimum value needed. In practice, one should try an initially small value of α, say 6, and when that fails to provide two-cuttability double the value for the lower subtree levels. In this manner, one can arrive at the true minimum value in O(log α) such iterations, if necessary, without having to calculate it. Since the minimum α needed in both cut sets is O(d2 ), this adds only an O(log(d)) factor to the depth.