algorithm design techniques in the worst casefor any point pi at most points pj are considered this is because these points must lie either in the -by- square in the left half of the strip or in the -by- square in the right half of the strip on the other handall the points in each -by- square are separated by at least in the worst caseeach square contains four pointsone at each corner one of these points is pi leaving at most seven points to be considered this worstcase situation is shown in figure notice that even though pl and pr have the same coordinatesthey could be different points for the actual analysisit is only important that the number of points in the -by- rectangle be ( )and this much is certainly clear because at most seven points are considered for each pi the time to compute dc that is better than is (nthuswe appear to have an ( log nsolution to the closestpoints problembased on the two half-sized recursive calls plus the linear extra work to combine the two results howeverwe do not quite have an ( log nsolution yet the problem is that we have assumed that list of points sorted by coordinate is available if we perform this sort for each recursive callthen we have ( log nextra workthis gives an ( log nalgorithm this is not all that badespecially when compared to the brute-force ( howeverit is not hard to reduce the work for each recursive call to ( )thus ensuring an ( log nalgorithm we will maintain two lists one is the point list sorted by coordinateand the other is the point list sorted by coordinate we will call these lists and qrespectively these can be obtained by preprocessing sorting step at cost ( log nand thus does not affect the time bound pl and ql are the lists passed to the left-half recursive calland pr and qr are the lists passed to the right-half recursive call we have already seen that is easily split in the middle once the dividing line is knownwe step through sequentiallyplacing each element in ql or qr as appropriate it is easy to see that ql and qr will be automatically sorted by coordinate when the recursive calls returnwe scan through the list and discard all the points whose coordinates are not within the strip then pl pl left half pr right half pl figure at most eight points fit in the rectanglethere are two coordinates shared by two points each