- #1
AkilMAI
- 77
- 0
Can someone please explain to me why the recursive part of this algorithm has the 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 floor function of T(n/2) and Tc(n/2) represents the the ceilling function
It is called Shamos algorithm and the main steps are:
1. If n ≤ 3 find the closest points by brute force and stop.
2. Find a vertical line V such that divides the input set into two disjoint subsets PL and PR of size
as equal as possible . Points to the left or on the line
belong PL and points to the right or on the line belong to PR. No point belongs to both since
the sets are disjoint.
3. Recursively find the distance δL of a closest pair of points in PL and the distance δR of a closest
pair in PR.
4. Let δ = min(δL, δR). The distance of a pair of closest points in the input set P is either that of
the points found in the recursive step (i.e., δ) or consists of the distance between a point in PL
and a point in PR.
(a) The only candidate points one from PL and one from PR must be in a vertical strip consisting
of a line at distance δ to the left of the line V and a line at distance δ to the right of V
(b) Let YV be an array of the points within the strip sorted by non-decreasing y coordinate
(i.e., if i ≤ j then YV ≤ YV [j]).
(c) Starting with the first point in YV and stepping trough all except the last, check the distance
of this point with the next 7 points (or any that are left if there are not as many as 7). If a
pair is found with distance strictly less than δ then assign this distance to δ.
5. Return δ.
Thanks.
T(n) = {O(1), if n ≤ 3;
{Tf(n/2) + Tc(n/2) + O(n), if n > 3.
->where Tf(n/2) represents the floor function of T(n/2) and Tc(n/2) represents the the ceilling function
It is called Shamos algorithm and the main steps are:
1. If n ≤ 3 find the closest points by brute force and stop.
2. Find a vertical line V such that divides the input set into two disjoint subsets PL and PR of size
as equal as possible . Points to the left or on the line
belong PL and points to the right or on the line belong to PR. No point belongs to both since
the sets are disjoint.
3. Recursively find the distance δL of a closest pair of points in PL and the distance δR of a closest
pair in PR.
4. Let δ = min(δL, δR). The distance of a pair of closest points in the input set P is either that of
the points found in the recursive step (i.e., δ) or consists of the distance between a point in PL
and a point in PR.
(a) The only candidate points one from PL and one from PR must be in a vertical strip consisting
of a line at distance δ to the left of the line V and a line at distance δ to the right of V
(b) Let YV be an array of the points within the strip sorted by non-decreasing y coordinate
(i.e., if i ≤ j then YV ≤ YV [j]).
(c) Starting with the first point in YV and stepping trough all except the last, check the distance
of this point with the next 7 points (or any that are left if there are not as many as 7). If a
pair is found with distance strictly less than δ then assign this distance to δ.
5. Return δ.
Thanks.