Monday, August 8, 2022

Number of segments derived from the glance function

For glance function H, with last jump at diameter, we have 

H(diameter)=number of segments

Several ways to see this is true without the (lost) argument by induction based on the (false) analysis of adding a new (segment+gap) at one end of the collection of (one fewer) segments. One is to simply examine the form of the glance function for these segments (N=3, diam=a+b+c+d+e):

With segments of lengths a, c, and e; separated by gaps of lengths b and d, then the glance function has rows with +/- jumps at these places (sorry about the shitty notation, inserting the "h" is awkward):

+a - (a+b) + (a+b+c) - (a+b+c+d) + (a+b+c+d)
       +b      -   (b+c)    + (b+c+d) - (b+c+d+e)
                       +c      -   (c+d)   + (c+d+e)
                                    +d     -    (d+e)
                                              + e
For each segment row: the row ends with + and all other +/- cancel. For a gap: all the +/- cancel. Hence the height of the glance function at (diam) is the same as the number of rows that start with a segment length - one per segment.

No comments:

Post a Comment