Here is a brief description of the layout of the Objects in my Project and how the binary search partition is built.

Overview of the Process

1. At the bottom we have points that are either read in or generated randomly
2. The points are collected into cells and the cells make up a grid. Each cell has a density, and number of points associated with it.
3. The grid is put into one bucket whose lowerBound and upperBound are not points, but are designated by cells in the grid. Therefore the lowerBound will always be (0,0,0,0) for the first bucket and (X,X,X,X) where X is the last cell in each dimension.
4. From here on, we deal only with cells
5. A bucket is created to contain all the cells
6. The bucket is split into two buckets until the desired number of buckets is reached.

=Defining the Cells=

The question is what parameters decide the cell size/shape and grid size and shape? We determine this in the following way:

1. Find the lower and upper bound points in each dimesion lowerBound = (wl,xl,yl,zl) and upperBound = (wu,xu,yu,zu). This may be given by the random point generating function, but most often is determined as we read the points.
2. Given the resolution of the grid we can now determine the size/shape of the cells.

= From bucket to buckets =

Next the question is how is the first bucket made and how do we split the into more buckets.

Each bucket has:

1. lowerBound and upperBound cells
2. cell partition
3. number of points
4. skew
5. skew reduction

The first bucket is made up of all the cells in the Grid4D object. Bucket = lowerBound(0,0,0,0) and upperBound(X,X,X,X). Notice that these are cell numbers not actual positions.

When a bucket is created it is given cell bounds and the following are calculated:

1. Number of points
2. Skew

Note that we CANNOT CALCULATE THE:

1. partition point - because this creates buckets and that would start an endless loop.
2. skew reduction - because this requires the partition point.

Partitioning the Bucket

A bucket must be refreshed - that is we must calculate the partitionPoint and skewReduction by calling refresh();

The bucket then has a patitionCell. The partitionCell is the upperBoundCell execept in the dimension it is split. When a bucket is split the lowerBucket and upperBucket are created as follows:

     lowerBucket = [lowerBoundCell, partitionCell]
     upperBucket = [lowerBoundCell except in the split dimension substitute partitionCell+1, upperBound]

Clearly than the calculation of the skew reduction must be done along this same split.