Let c be the left upper corner of rectangle s. s adds a new intersection to all polygons below c, the polygon containing c is split into two and the cover-variables of all of them increase by one. Note that a new locally maximal polygon might arise below c. All false maxima below c become 'true' maxima again. They are deleted from LF and inserted again into LM. The operation can be performed by locating the polygon to be split by binary search in L, scanning the list LF until the y-coordinate of c is reached, and inserting all false maxima back into LM.