Runtime explanation

Question

Can someone explain to me why the recursive part of this algorithm has runtime

T (n) = {O (1) if n ≤ 3; {Tf (n / 2) + Tc (n / 2) + O (n) if n> 3.

-> where Tf (n / 2) represents the sex function T (n / 2) and Tc (n / 2) represents the flooding function <? p <

The algorithm is called Shamos, and the main steps are:

• If n ≤ 3, find the nearest point using brute force and stop.
• Find the vertical line V that divides the input set into two disjoint subsets of PL and PR sizes as much as possible. Points to the left or to the line belong to PL and point to the right or to the line belong to PR. None of the items apply to both, since the sets do not intersect.
• Recursively find the distance δL of the nearest pair of points in PL and the distance δR of the nearest pair in PR.

• Let δ = min (δL, δR). The distance of a pair of nearest points on the input set P is equal to the distance from a pair of points found at the recursive stage (i.e., δ), or consist of the distance between a point in PL and a point in PR.

  (a) The only candidate indicates one of PL and one of PR must be in a vertical strip consisting of a line at a distance δ to the left of line V and a line at a distance of δ to the right of V

  (b) Let YV be an array of points in the strip sorted by the non-decreasing coordinate y (that is, if I ≤ j, then YV [i] ≤ YV [j]).

  (c) Starting from the first point in YV and stepping through everything except the last, check the distance from this point with the following 7 points (or the rest if there are no more than 7 of them). If the pair is located with a distance strictly smaller than δ, then assign this distance to δ.

• Return δ. Thank you in advance.

Answer 1

T(c(n/2)) and T(f(n/2)) describe how long it takes to recursively call the algorithm in the left and right groups, since half of the points were placed in each group.

O(n) comes from the complex part of the algorithm: after recursive calls, we found δ, namely the distance between the nearest pair of points in either the left or right group. Now we want to find pairs consisting of one point from the left group and one point from the right group. Of course, it makes little sense to look at points that are farther than δ from the midline. However, it may still be that all points are within δ of the midline, so it seems to us that we have to compare pairs of points t23. The important point now is that it is precisely because we know that in each group no pair of points is closer than δ, we know that there is a small, constant worst-case limit on how many points from the right group we need to look for each pair in the left group. Therefore, if we can only sort our points by their y coordinates, we can find the closest pair in linear time. It is possible to get this sorted list in linear time due to the way the list is transferred between recursive calls, but the details will leave me (feel free to fill in, anyone).