Derivation of the stepping algorithm

The stepping algorithm was devised by Luca Furini, and is described on the page TableLayout/KnuthElementsForTables. On this page we show how the algorithm can be derived.

We step through the table from one possible breakpoint to the next. This algorithm specifies how to assign Knuth elements at each possible breakpoint.

We define the following quantities:

Note that maxRemainingHeight-0 = noBreakHeight.

The assigned Knuth boxes and penalties together make up the step height:

totalBoxHeight-i + penaltyHeight-i = stepHeight-i

The strategy of the algorithm is to split the step height between the boxes and a penalty as follows: the penalty is equal to the extra height that is caused by this page break. That is:

penaltyHeight-i = stepHeight-i + maxRemainingHeight-i - noBreakHeight

Therefore:

totalBoxHeight-i = noBreakHeight - maxRemainingHeight-i

This means that the total box height is that part of the no-break height that at this step definitely appears before the page break.

The penalty height at each step can be calculated from the above formula. The box height at each step can be calculated as follows:

boxHeight-i
        = totalBoxHeight-i - totalBoxHeight-(i-1)
        = noBreakHeight - maxRemainingHeight-i
          - (noBreakHeight - maxRemainingHeight-(i-1))
        = maxRemainingHeight-(i-1) - maxRemainingHeight-i
        = prevMaxRemainingHeight-i - maxRemainingHeight-i

or as follows:

boxHeight-i + totalBoxHeight-(i-1)
        = noBreakHeight - maxRemainingHeight-i
=>
boxHeight-i
        = noBreakHeight - maxRemainingHeight-i - totalBoxHeight-(i-1)
        = noBreakHeight - maxRemainingHeight-i - prevTotalBoxHeight-i

The algorithm can also be derived by reverting the logic of the derivation: The strategy of the algorithm is to split the step height between the boxes and a penalty as follows: The total box height is equal to that part of the height that definitively appears before the page break. That is:

totalBoxHeight-i = noBreakHeight - maxRemainingHeight-i

Therefore:

penaltyHeight-i = stepHeight-i + maxRemainingHeight-i - noBreakHeight

TableLayout/KnuthElementsForTables/SteppingAlgorithmDerivation (last edited 2009-09-20 23:52:17 by localhost)