In mathematics, the boustrophedon transform is a procedure which maps one sequence to another. The transformed sequence is computed by an "addition" operation, implemented as if filling a triangular array in a boustrophedon manner -- as opposed to a "Raster Scan" sawtooth-like manner.
Definition
The boustrophedon transform is a numerical, sequence-generating transformation, which is determined by an "addition" operation. Generally speaking, given a sequence:, the boustrophedon transform yields another sequence:, where is likely defined equivalent to. The entirety of the transformation itself can be visualized as being constructed by filling-out the triangle as shown in Figure 1.
Boustrophedon Triangle
To fill-out the numerical Isosceles triangle, you start with the input sequence,, and place one value per row, using the boustrophedon scan approach. The top vertex of the triangle will be the input value, equivalent to output value, and we number this top row as row 0. The subsequent rows are numbered consecutively as integers -- let denote the number of the row currently being filled. These rows are constructed according to the row number as follows:
For all rows, numbered, there will be exactly values in the row.
If is odd, then put the value on the right-hand end of the row.
* Fill-out the interior of this row from right-to-left, where each value is the result of "addition" between the value to right and the value to the upper right.
* The output value will be on the left-hand end of an odd row.
If is even, then put the input value on the left-hand end of the row.
* Fill-out the interior of this row from left-to-right, where each value is the result of "addition" between the value to its left and the value to its upper left.
* The output value will be on the right-hand end of an even row.
Refer to the arrows in Figure 1 for a visual representation of these "addition" operations. For a given, finite input-sequence:, of values, there will be exactly rows in the triangle, such that is an integer in the range: . In other words, the last row is.
Recurrence relation
A more formal definition uses a recurrence relation. Define the numbers by Then the transformed sequence is defined by . Per this definition, note the following definitions for values outside the restrictions on pairs:
Building from the geometric design of the boustrophedon transform, algebraic definitions of the relationship from input values to output values can be defined for different algebras.
Euclidean (Real) values
In the Euclidean Algebra for Real -valued scalars, the boustrophedon transformed Real-value is related to the input value,, as: with the reverse relationship defined as: where is the sequence of "up/down" numbers -- also known as secant or tangent numbers.
The exponential generating function of a sequence is defined by The exponential generating function of the boustrophedon transform is related to that of the original sequence by The exponential generating function of the unit sequence is 1, so that of the up/down numbers is sec x + tan x.
