8.3. Kinetic Segment Tree

By turning the static segment tree into a kinetic one, we are moving one step closer to our final goal of a kinetic BSP [de Berg et al. 01].

Now segments (i.e., intervals on ) can move freely they can swap positions , they can shorten or lengthen, etc. Observe, however, that the situation is not as difficult as it might seem, because of the following:

During the construction of the static segment tree, we never really needed to know the exact values of the endpoints of the intervals; it was completely sufficient to know their position in the sorted list of all endpoints;
For each segment s , there is a certain amount > 0 by which we can move s without invalidating the segment tree;
Whatever the position of a certain number segments, the skeleton of the segment tree is always the same. The only thing that changes is the labeling of the nodes with segment IDs.

These observations give rise to the following modifications of the original segment tree data structure:

Segments are defined as s _i := ( a _i , b _i ) , a _i ,B _i ˆˆ , 1 ‰ a _i , b _i ‰ 2 n . a _i , b _i are called the rank of the endpoints;
An array R [1 , , 2 n ] stores the current values of the endpoints (so the interval for s _i is given by , ). This array is kept sorted by value;
With each segment s , we maintain a fragment list ( s ) := { s ˆˆ S ( )}. is kept sorted from left to right;
For each elementary interval [ i, i + 1], we store a pointer to its associated leaf _i .

The certificates in this KDS are Z _i := R _i < R _i ₊₁ , i = 1 , , 2 n ˆ 1. The proof remains valid until two endpoints swap position in array R . In that case, exactly two certificates are affected. The ranks of all other interval endpoints remain the same, so they are associated with the same nodes in the tree (in other words, their fragment lists remain the same).

Let s be one of the two intervals affected by an endpoint swap. ^[1] There are four possible cases for which endpoints have swapped and how. Consider the one where before s = [ i, j ] and after the swap s = [ i, j + 1] (and analogously for the other segment).

The nave update algorithm would just delete both segments from all nodes (with the help of array ), and then sift them top-down through the tree. This would yield an O (log n ) complexity.

But we can do better. The idea is to augment the segment s = [ i, j ] by just the EI [ j, j + 1], and then just update the tree starting with _j , which is the leaf for [ j, j + 1], and which is now covered by s , too. The pseudocode shown in Algorithm 8.3 gives more details.

Algorithm 8.3: Updating a kinetic segment tree.

 1:           _j {leaf of [  j, j  + 1]} 2:  repeat  3:       sibling of     4:  if   s     S  (     )  then  5:                    delete  s  from  S  (     ) 6:       parent(     ) 7:  end if  8:  until   s      S  (     ) 9: insert  s  into  S  (     )

Analogously, we can traverse the segment tree bottom-up in order to augment the other segment by an EI. Note that the test in Step 4 is necessarily false if is a left child.

The running time of Algorithm 8.3 is O ( h ), where h is the height of the node that gets s attached, i.e., [ j, j + 1] ˆˆ Int( ) and s ˆˆ S ( ) (after the update). This is made possible by the array , which allows us to perform Step 4 in Algorithm 8.3 in time O (1). When starting with the leaf of the EI, we just need to inspect the front/back of , and then we work our way through .

Lemma 8.1. Let S be a set of n moving segments on the real line . There is a kinetic segment tree with O ( n log n ) space, which can be updated in expected time O (1) when an event occurs (i.e., two endpoints swap position). The worst-case time is still O (log n ) . The KDS is local and efficient.

Locality and efficiency are given, since any segment participates in at most four certificates, and there are no internal events. The O (1) time bound can be proven fairly easily by showing that the average height in a balanced tree is O (1).

Figure 8.2 shows an example how the labeling changes as a result of an event.

Figure 8.2: An example of a segment tree over four segments. The dashed segments show the segments 4 and 2, respectively, after two of their endpoints have swapped position. The changes in the tree are highlighted with dashed boxes.

^[1] We omit the case where both endpoints belong to the same interval, as this is fairly easy to deal with.