One possible event is the creation/removal of a polygon adjacent to corner c of a single maximum in the list LD. Possibly one new block is created by splitting an old block into two. After having located the position of the block, corresponding to the y-coordinate of c, by binary search, this can be done in constant time. Clearly there are at most O(n) such events.