Formal Statement of Algorithm

We have:

1. A set of points on a plane $(u_j , v_j )$, $j=1 \ldots n$.

2. An array of weights $W_j$, $j=1 \ldots n$, one for each point $(u_j , v_j )$.

3. Parameter space $(\alpha , \beta )$, restricted to the rectangle $\alpha_1 \leq \alpha \leq \alpha_2$, $\beta_1 \leq \beta \leq \beta_2$.

4. A vote threshold $T$.

5. A maximum level of subdivision $l_{\max}$.

The algorithm is as follows:

begin

Declare new variables:

Arrays ${\bf I}^{\rm low}$ and ${\bf I}^{\rm high}$ of intercepts $I^{\rm low}_j$, $I^{\rm high}_j$, $j=1 \ldots n$.

An array ${\bf P}$ of boolean flags $P_1, P_2,\ldots,P_n$.

Integer variables $max\_level$ and $max\_value$.

Variables $\alpha_{\rm best}$ and $\beta_{\rm best}$ comprising a point in $(\alpha , \beta )$ space.

Another array of flags ${\bf P}_{\rm best}$.

Boolean flags $s_{00}$, $s_{01}$, $s_{10}$ and $s_{11}$.

The variables $max\_level$, $max\_value$, $\alpha_{\rm best}$, $\beta_{\rm best}$ and array ${\bf P}_{\rm best}$ are used to keep track of the best fit as the algorithm proceeds.

Set all the $P_j$ to $false$.

For each point $(u_j , v_j )$:

begin

Set flags corresponding to intercepts lying below/above vertices of the root rectangle:

if $v_j - \alpha_1 u_j - \beta_1 > 0$ set $s_{00}$ to $false$, otherwise set it to $true$.

if $v_j - \alpha_2 u_j - \beta_1 > 0$ set $s_{01}$ to $false$, otherwise set it to $true$.

if $v_j - \alpha_1 u_j - \beta_2 > 0$ set $s_{10}$ to $false$, otherwise set it to $true$.

if $v_j - \alpha_2 u_j - \beta_2 > 0$ set $s_{11}$ to $false$, otherwise set it to $true$.

If the $s$'s are either all true or all false, the line $\beta = -u_j \alpha + v_j$ misses the root rectangle, otherwise they intersect. If they intersect, set $I^{\rm low}_j$ to $v_j - \alpha_1 u_j$, $I^{\rm high}_j$ to $v_j - \alpha_2 u_j$ and $P_j$ to $true$.

end

Call the procedure $divide\_rectangle$ with arguments as follows:

1. Array of flags ${\bf P}$.

2. Arrays ${\bf I}^{\rm low}$ and ${\bf I}^{\rm high}$.

3. Variables $\beta_1$ and $\beta_2$.

4. Initial level of subdivision 0.

5. Initial accumulator value 0.

6. Empty line of descent list.

end

Procedure $divide\_rectangle$ ( array of flags ${\bf P}$, arrays of intercepts ${\bf I}^{\rm low}$ and ${\bf I}^{\rm high}$, variables $\beta_{\rm low}$ and $\beta_{\rm high}$, subdivision level $l$, accumulator value $v$, line of descent list ):

begin

Declare new variables:

Boolean flag arrays ${\bf P}^{00}$, ${\bf P}^{01}$, ${\bf P}^{10}$ and ${\bf P}^{11}$ each with $n$ elements. All the elements of the flag arrays are initialised to $false$.

Array ${\bf I}^{\rm av}$ of $\beta$ intercepts with $n$ elements.

Accumulators $A_{00}$, $A_{01}$, $A_{10}$ and $A_{11}$, initialised to zero.

Variable $\beta_{\rm av}$.

Nine boolean flags $v_{ll}$, $v_{la}$, $v_{lh}$, $v_{al}$, $v_{aa}$, $v_{ah}$, $v_{hl}$, $v_{ha}$, $v_{hh}$.

Boolean flag $s$, initialised to $false$.

Set $\beta_{\rm av}$ to $(\beta_{\rm low} + \beta_{\rm high})/2$.

Sum the votes for the child rectangles: For each $j$ such that $P_j = true$:

begin

Set flags $v_{ll}$, $v_{la}$ etc. to $false$.

Set $I^{\rm av}_j$ to $(I^{\rm low}_j + I^{\rm high}_j)/2$.

If $\beta_{\rm low} < I^{\rm low}_j$ then:

begin

Set $v_{ll}$ to $true$.

If $\beta_{\rm av} < I^{\rm low}_j$ then:

begin

Set $v_{la}$ to $true$.

If $\beta_{\rm high} < I^{\rm low}_j$ then set $v_{lh}$ to $true$.

end

end

Repeat for intercept $I^{\rm av}_j$ and flags $v_{al}$, $v_{aa}$ and $v_{ah}$.

Repeat for intercept $I^{\rm high}_j$ and flags $v_{hl}$, $v_{ha}$ and $v_{hh}$.

end

If $v_{ll}$, $v_{la}$, $v_{al}$ and $v_{aa}$ are not all either $true$ or $false$:

begin

Add weight $W_j$ to $A_{00}$

Set flag $P^{00}_j$ to $true$.

end

Repeat for flags $v_{la}$, $v_{lh}$, $v_{aa}$ and $v_{ah}$, accumulator $A_{01}$ and flag $P^{01}_j$.

Repeat for flags $v_{al}$, $v_{aa}$, $v_{hl}$ and $v_{ha}$, accumulator $A_{10}$ and flag $P^{10}_j$.

Repeat for flags $v_{aa}$, $v_{ah}$, $v_{ha}$ and $v_{hh}$, accumulator $A_{11}$ and flag $P^{11}_j$.

end

Subdivide child rectangles receiving greater than or equal to $T$ votes: If $l < l_{\rm best}$:

begin

If $A_{00} \geq T$ recursively subdivide child rectangle:

begin

Add [-1,-1] to original line of descent.

Call $divide\_rectangle$ with arguments ${\bf P}^{00}$, ${\bf I}^{\rm low}$, ${\bf I}^{\rm av}$, $\beta_{\rm low}$, $\beta_{\rm av}$, $A_{00}$, $l+1$ and extended line of descent.

Set flag $s$ to $true$.

end

Repeat with accumulator $A_{01}$, index pair [-1,1], flag list ${\bf P}^{01}$, intercept arrays ${\bf I}^{\rm low}$ and ${\bf I}^{\rm av}$, and $\beta$ values $\beta_{\rm av}$ and $\beta_{\rm high}$.

Repeat with accumulator $A_{10}$, index pair [1,-1], flag list ${\bf P}^{10}$, intercept arrays ${\bf I}^{\rm av}$ and ${\bf I}^{\rm high}$, and $\beta$ values $\beta_{\rm low}$ and $\beta_{\rm av}$.

Repeat with accumulator $A_{11}$, index pair [1,1], flag list ${\bf P}^{11}$, intercept arrays ${\bf I}^{\rm av}$ and ${\bf I}^{\rm high}$, and $\beta$ values $\beta_{\rm av}$ and $\beta_{\rm high}$.

If $s$ is still $false$ (i.e. no further subdivision of this rectangle), test for best fit so far:

If $l > max\_level$ or if $l = max\_level$ and $v > max\_value$:

begin

Set $max\_level$ to $l$.

Set $max\_value$ to $v$.

Calculate centre of rectangle in $\alpha$ direction by calling procedure $alpha\_centre$ with the line of descent as argument. The result is copied into $\alpha_{\rm best}$.

Set $\beta_{\rm best}$ to $\beta_{\rm av}$.

Copy array of flags ${\bf P}$ into array ${\bf P}_{\rm best}$.

end

end (procedure $divide\_rectangle$)

Procedure $alpha\_centre$ ( line of descent list ): begin

Declare new variables:

Array ${\bf r}_{\alpha}$ of three elements with indices -1, 0 and 1. The zero (middle) element of ${\bf r}_{\alpha}$ is not used.

Set array ${\bf r}_{\alpha}$ as follows:

$$r_{\alpha}(-1) = \frac{\alpha_1 - \alpha_2}{4},\;\; r_{\alpha}(1) = \frac{\alpha_2 - \alpha_1}{4}.$$

Set $\alpha_{\rm best}$ to zero.

While line of descent not traversed (i.e. root rectangle not yet reached):

begin

Take next pair of indices $[b_1,b_2]$ on line of descent.

Replace old value of $\alpha_{\rm best}$:

$$\alpha_{\rm best} \leftarrow \frac{\alpha_{\rm best}}{2} + r_{\alpha}(b_1).$$

end

Add centre $\alpha$-coordinate of root cube to $\alpha_{\rm best}$:

$$\alpha_{\rm best} \leftarrow \alpha_{\rm best} + \frac{\alpha_1 + \alpha_2}{2}.$$

end (procedure $alpha\_centre$)

At the end of the algorithm $max\_level$ is the highest level of subdivision reached, $max\_value$ the highest accumulator value at level $max\_level$, while $\alpha_{\rm best}$ and $\beta_{\rm best}$ hold the best fit line parameters.

Note that the points $(u_j , v_j )$ are never used by the procedure $divide\_rectangle$. All the information about the points is contained in the intercept arrays. The $\beta$ index part of the line of descent is actually superflous since the $\beta$ positions of rectangles are passed from parent to child via $\beta_{\rm low}$ and $\beta_{\rm high}$.