2. X intersects either all bases and/or all hypotenuses. This is the case if X's basis is lower than the lowest basis in C and X's upper point is higher than the highest basis, and/or X's basis is lower than the lowest hypotenuse and its upper point is higher than C's highest hypotenuse. Both can be checked in O(1). If this is the case, X has just to be added to C. To insert X's basis and hypotenuse at the correct place, a binary search with X's height of the basis and the height of its hypotenuse is accomplished in O(log n) for every clique it is added to, i.e. with a runtime of at most O(|Q| log n) per birth event.