 Therefore, it is sufficient to compute at most left-right distances in step 4.The recurrence relation for the number of steps can be written as , which we can solve using the master theorem for divide-and-conquer recurrences to get .As the closest pair of points define an edge in the Delaunay triangulation, and correspond to two adjacent cells in the Voronoi diagram, the closest pair of points can be determined in linear time when we are given one of these two structures.