content_image/299146.jpg
Since, in the univariate case, D$_{X}$ ( x$_{i}$,x$_{k}$ ) < D$_{X}$ ( x$_{i}$,x$_{j}$ ) is equivalent to | x$_{k}$ − x$_{i}$ | < | x$_{j}$ − x$_{i}$ | , and similarly for y , partition cells are simply axis-aligned rectangles, as in the distribution-free test. Here, however, only sample j is a vertex, and sample i is the center of mass. The diagonal-opposing vertex from j may not even be a point in the sample, and thus is not directly captured by A . Still, the appropriate point to sample A in, for computing the contingency table cell in O (1), can be found in O (1) additional amortized time, as follows: 

1. Sort once the unique values of x , and do the same for y . 

2. When traversing all pairs, first traverse i . 

2.1 For every i , traverse the sorted values of x with two concurrent iterators starting from x$_{i}$ , one moving right (i.e., from low to high x ) and one ad- vancing left. 

2.2 Subsequently to each step taken with the right iterator, arriving at an x$_{j}$ , advance the left iterator until a value is encountered which is farther from x$_{i}$ than x$_{j}$ is, and this is the opposing vertex x coordinate value for the rectangle for the pair i,j . 

The process, which is depicted in Figure 8, takes O ( N ) time for N values, and is repeated for the y axis. 

<img src='content_image/299146.jpg'>

