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