we are required to find the closest pair of points it is possible that two points have the same positionin that casethat pair is the closestwith distance zero if there are pointsthen there are ( )/ pairs of distances we can check all of theseobtaining very short programbut at the expense of an ( algorithm since this approach is just an exhaustive searchwe should expect to do better let us assume that the points have been sorted by coordinate at worstthis adds ( log nto the final time bound since we will show an ( log nbound for the entire algorithmthis sort is essentially freefrom complexity standpoint figure shows small sample point setp since the points are sorted by coordinatewe can draw an imaginary vertical line that partitions the point set into two halvespl and pr this is certainly simple to do now we have almost exactly the same situation as we saw in the maximum subsequence sum problem in section either the closest points are both in pl or they are both in pr or one is in pl and the other is in pr let us call these distances dl dr and dc figure shows the partition of the point set and these three distances we can compute dl and dr recursively the problemthenis to compute dc since we would like an ( log nsolutionwe must be able to compute dc with only (nadditional work we have already seen that if procedure consists of two half-sized recursive calls and (nadditional workthen the total time will be ( log nlet min(dl dr the first observation is that we only need to compute dc if dc improves on if dc is such distancethen the two points that define dc must be within of the dividing linewe will refer to this area as strip as shown in figure this observation limits the number of points that need to be considered (in our cased dr there are two strategies that can be tried to compute dc for large point sets that are uniformly distributedthe number of pointsthat are expected to be in the strip is very small indeedit is easy to argue that only onpoints are in the strip on average thuswe could perform brute-force calculation on these points in (ntime the pseudocode figure small point set