Differences between revisions 1 and 2
Revision 1 as of 2005-05-16 18:17:56
Size: 2706
Editor: pm31-60
Revision 2 as of 2009-09-20 23:52:17
Size: 2706
Editor: localhost
Comment: converted to 1.6 markup
No differences found!

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:

  • noBreakHeight is the height without page breaks

  • stepHeight-i is the height before the page break at step i

  • maxRemainingHeight-i is the height after the page break at step i

  • penaltyHeight-i is the height of the penalty at step i

  • boxHeight-i is the height of the box at step i

  • totalBoxHeight-i = Sum(j=1 .. i) boxHeight-j

  • prevTotalBoxHeight-i = totalBoxHeight-(i-1)

  • prevMaxRemainingHeight-i = maxRemainingHeight-(i-1)

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


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:

        = 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
        = 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


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

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