Divide & Conquer Order Statistics
2021-01-13 CSC373 Winter 2021 – Sam Toueg 1
Overview and Motivation
𝐴=𝑎!,𝑎”,𝑎#,…,𝑎$ (unsorted) • Find average of 𝐴: linear time • Find max/min of 𝐴: linear time
• Find median of 𝐴: linear time ?
ØIntuitively: median of 𝐴 = “middle element in sorted 𝐴” ØFormally: let Π be a permutation of 1, … , 𝑛, that sorts 𝐴
𝑎!” ≤𝑎!# ≤…≤𝑎!$; median of 𝐴 = 𝑎! !”
2021-01-13 CSC373 Winter 2021 – Sam Toueg 2
Algorithms for finding median of 𝐴
• Trivial algorithm: sort 𝐴, then get the median
Ø𝑂(𝑛𝑙𝑜𝑔𝑛)
• Is there an 𝑂 𝑛 algorithm?
• To find median of 𝐴, solve a more general problem:
Select(𝐴,𝑘)
ØInput: 𝐴 = 𝑎”,𝑎#,𝑎%,…,𝑎$ and 1 ≤ 𝑘 ≤ 𝑛 ØOutput: 𝑘th-smallest element of 𝐴
ØE.g., 𝐴 = 5, 2, 6, 7, 4 Select(𝐴,1) = 2 and Select(𝐴,4) = 6 ØFor simplicity we will assume the 𝑎&‘s are distinct
2021-01-13 CSC373 Winter 2021 – Sam Toueg 3
Select(𝐴,𝑘)
Input: 𝐴 = 𝑎!,𝑎”,𝑎#,…,𝑎$;1 ≤ 𝑘 ≤ 𝑛 Output: 𝑘th-smallest element of 𝐴
If 𝐴 =1,thenreturn𝐴[1] Else
𝑠 ← arbitrary element of 𝐴 (𝑠 is the “splitter”) 𝐴’ ← sublist of 𝐴 with elements < 𝑠
𝐴( ← sublist of 𝐴 with elements > 𝑠
If 𝑘 < |𝐴'| + 1 then return Select(𝐴',𝑘)
If 𝑘 = |𝐴'| + 1 then return 𝑠
If 𝑘 > |𝐴’| + 1 then return Select(𝐴+, 𝑘 − |𝐴’| − 1)
Note: If the splitter 𝑠 is the 𝑖th smallest element in 𝐴, then 𝑇 𝑛 =𝑇[max(𝑖−1,𝑛−𝑖)]+𝑐𝑛
What is the worst choice of 𝑠? Best choice of s?
2021-01-13 CSC373 Winter 2021 – Sam Toueg 4
Running time 𝑇 𝑛 of Select(𝐴,𝑘) • If the splitter 𝑠 is the 𝑖th smallest in 𝐴:
Ø𝑇 𝑛 =𝑇[max(𝑖−1,𝑛−𝑖)]+𝑐𝑛
• Worst choice for 𝑠: the min/max of 𝐴
ØInthiscase𝑇 𝑛 =𝑇 𝑛−1 +𝑐𝑛=Θ(𝑛#) • Best choice for 𝑠 : the median of 𝐴
ØInthiscase𝑇 𝑛 =𝑇 $# +𝑐𝑛 =Θ(𝑛) • Note that for any 𝑏 > 1 (even 1.01!):
Ø 𝑇 𝑛 = 𝑇 $) + 𝑐 𝑛 = Θ ( 𝑛 )
2021-01-13 CSC373 Winter 2021 – Sam Toueg 5
𝑎=1 𝑏=2 𝑑=1
by master theorem (𝑎 < 𝑏!)
𝑎=1 𝑏>1 𝑑=1 by master
theorem (𝑎 < 𝑏!)
Select splitter 𝑠 uniformly at random
• Definition: 𝑠 is a good splitter if
Ø𝑠 is greater than 1⁄4 elements of 𝐴, and Ø𝑠 is smaller than 1⁄4 elements of 𝐴
1/4 Sorted 𝐴
1/4
Good 𝒔
ØOBS1: A good splitter reduces input size from 𝑛 to ≤ %2 𝑛
ØOBS2: Half of the elements are good splitters • Prob[choosing a good splitter] = 𝑝 = "#
•Probchoosingabadsplitter =𝑞=1−𝑝="#
2021-01-13 CSC373 Winter 2021 - Sam Toueg 6
Expected running time
• Random variable 𝑧 = # of trials till obtaining a good splitter (a ``success’’)
Ø𝑧 has values in range {1, 2, ... } ØProb𝑧=𝑘 =𝑞5'"Z𝑝
•𝐸𝑧 =∑7 𝑘ZProb[𝑧=𝑘] 56"
• = ∑7 𝑘 Z [𝑞5'" Z 𝑝] 56"
[geometricdistribution]
• = 8 ∑7
9 56"
𝑘 Z 𝑞5
•=8Z9=8Z9=" 9"'9" 98" 8
• Thus, for 𝑝 = !" , the expected number of trials till obtaining a good splitter is 2
2021-01-13 CSC373 Winter 2021 - Sam Toueg 7
Expected running time
What is the total number of steps taken by Select(𝐴,𝑘)?
<<<<<<< 𝑛"=𝑛𝑛0 𝑛1 𝑛2 𝑛3 𝑛4 𝑛5 𝑛6
...
...
Phase 0 Phase 1 Phase 2
size ≤(*+)𝑛 • Phase 𝑗: input size ≤ (%2):𝑛
size ≤ (*+),𝑛 • Rand var 𝑦: = # of recursive calls in phase 𝑗
size ≤ 𝑛
ØNote E 𝑦! = 2 (does not depend on 𝑗)
• Rand var 𝑥: = # of steps by all recursive calls in phase 𝑗
ØTotal number of steps by Select(𝐴,𝑘) is: 𝑥 = 𝑥" + 𝑥# + 𝑥$ + ⋯
• Wewanttocompute𝐸 𝑥 =𝐸[𝑥?]+𝐸[𝑥"]+⋯+𝐸[𝑥:]+⋯ 2021-01-13 CSC373 Winter 2021 - Sam Toueg 9
Expected running time
• 𝑥: = # of steps in all recursive calls in phase 𝑗
= # of recursive calls in phase 𝑗 ✕ # of steps in each
recursive call in phase 𝑗 𝑦- 3-
≤𝑐B4𝑛
•𝐸𝑥%≤𝐸𝑦%2𝑐#& 𝑛 becauseE𝑦%=2
• # of total steps taken by Select(𝐴,𝑘) is the random variable:
• 𝑥% ≤ 𝑦% 2 𝑐 # % 𝑛 &%
≤2𝑐 # %𝑛 &
• 𝑥=𝑥'+𝑥!+𝑥"+⋯ •𝐸𝑥=∑𝐸[𝑥]≤∑(2𝑐(#)%𝑛=2𝑐𝑛∑((#)%=2𝑐𝑛2 ! =8𝑐𝑛
%%%& %& !)!"=𝑂𝑛! 2021-01-13 CSC373 Winter 2021 - Sam Toueg 10
Deterministic Algorithm for Select(𝐴,𝑘)
• Select(𝐴,𝑘)
if 𝐴 ≤5thensort𝐴andreturn𝑘thsmallest Partition 𝑛 elements of 𝐴 into $* groups of size 5 each
Find median of each group by sorting the group
find a good splitter 𝑠 (deterministically) 𝑀 ⟵ list of these medians
𝑠 ⟵ D-Select(𝑀, |,| ) )"
𝐴 ← sublist of 𝐴 with elements < 𝑠
𝐴- ← sublist of 𝐴 with elements > 𝑠
If 𝑘 < |𝐴)| + 1 then return Select(𝐴),𝑘)
If 𝑘 = |𝐴)| + 1 then return 𝑠
If 𝑘 > |𝐴)| + 1 then return Select(𝐴-,𝑘 − |𝐴)| − 1 )
2021-01-13 CSC373 Winter 2021 – Sam Toueg 11
Deterministic Algorithm for Select(𝐴,𝑘) • find a good splitter 𝑠
Partition 𝑛 elements of 𝐴 into $* groups of size 5 each
●●●
●●●
●●●
●●●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
2021-01-13
CSC373 Winter 2021 – Sam Toueg 12
Deterministic Algorithm for Select(𝐴,𝑘)
• find a good splitter 𝑠
Partition 𝑛 elements of 𝐴 into $* groups of size 5 each Find median of each group by sorting the group
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
2021-01-13 CSC373 Winter 2021 – Sam Toueg 13
Deterministic Algorithm for Select(𝐴,𝑘)
• find a good splitter 𝑠
Partition 𝑛 elements of 𝐴 into $* groups of size 5 each
Find median of each group by sorting the group 𝑀 ⟵ list of these medians
𝑠 ⟵ Find median of 𝑀
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
●
●
●
●
●
●
𝑀
2021-01-13 CSC373 Winter 2021 – Sam Toueg 14
Deterministic Algorithm for Select(𝐴,𝑘)
• find a good splitter 𝑠
Partition 𝑛 elements of 𝐴 into $* groups of size 5 each
Find median of each group by sorting the group 𝑀 ⟵ list of these medians
𝑠 ⟵ Select(𝑀, |,| ) ”
Claim: 𝑠 is a good splitter
Ø greater than 1⁄4 elements of 𝐴
𝑀
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
● <●𝑠<● ∧∧∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
●
●
●
●
●
●
2021-01-13 CSC373 Winter 2021 - Sam Toueg 15
Deterministic Algorithm for Select(𝐴,𝑘)
• find a good splitter 𝑠
Partition 𝑛 elements of 𝐴 into $* groups of size 5 each
Find median of each group by sorting the group 𝑀 ⟵ list of these medians
𝑠 ⟵ Select(𝑀, |,| ) "
Claim: 𝑠 is a good splitter
Ø greater than 1⁄4 elements of 𝐴
𝑀
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
● <●𝑠<● ∧∧∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
●
●
●
●
●
●
2021-01-13 CSC373 Winter 2021 - Sam Toueg 16
Deterministic Algorithm for Select(𝐴,𝑘)
• find a good splitter 𝑠
Partition 𝑛 elements of 𝐴 into $* groups of size 5 each
Find median of each group by sorting the group 𝑀 ⟵ list of these medians
𝑠 ⟵ Select(𝑀, |,| ) "
Claim: 𝑠 is a good splitter
Ø greater than 1⁄4 elements of 𝐴 Ø smaller than 1⁄4 elements of 𝐴
elements ≤ s
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
● <●𝑠<● ∧∧∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
●
●
●
●
●
●
𝑀
2021-01-13 CSC373 Winter 2021 - Sam Toueg 17
Deterministic Algorithm for Select(𝐴,𝑘)
• find a good splitter 𝑠
Partition 𝑛 elements of 𝐴 into $* groups of size 5 each
Find median of each group by sorting the group 𝑀 ⟵ list of these medians
𝑠 ⟵ Select(𝑀, |,| ) "
Claim: 𝑠 is a good splitter
Ø greater than 1⁄4 elements of 𝐴 Ø smaller than 1⁄4 elements of 𝐴
elements ≤ s
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
● <●𝑠<● ∧∧∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
●
●
●
●
●
●
𝑀
2021-01-13 CSC373 Winter 2021 - Sam Toueg 18
Deterministic Algorithm for Select(𝐴,𝑘)
• find a good splitter 𝑠
Partition 𝑛 elements of 𝐴 into $* groups of size 5 each
Find median of each group by sorting the group 𝑀 ⟵ list of these medians
𝑠 ⟵ Select(𝑀, |,| ) "
Claim: 𝑠 is a good splitter
Ø greater than 1⁄4 elements of 𝐴 Ø smaller than 1⁄4 elements of 𝐴
elements ≤ s
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
● <●𝑠<● ∧∧∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
∧
●
●
●
●
●
●
●
𝑀
2021-01-13 CSC373 Winter 2021 - Sam Toueg
elements ≥ s
19
Deterministic Algorithm for Select(𝐴,𝑘)
• Select(𝐴,𝑘)
if 𝐴 ≤5thensort𝐴andreturn𝑘thsmallest Partition 𝑛 elements of 𝐴 into $* groups of size 5 each
Find median of each group by sorting the group
find a good splitter 𝑠
𝑀 ⟵ list of these medians
𝑠 ⟵ D-Select(𝑀, |,| ) )"
𝐴 ← sublist of 𝐴 with elements < 𝑠
𝐴- ← sublist of 𝐴 with elements > 𝑠
If 𝑘 < |𝐴)| + 1 then return Select(𝐴),𝑘)
If 𝑘 = |𝐴)| + 1 then return 𝑠
If 𝑘 > |𝐴)| + 1 then return Select(𝐴-,𝑘 − |𝐴)| − 1 )
2021-01-13 CSC373 Winter 2021 – Sam Toueg 20
Deterministic Algorithm for Select(𝐴,𝑘)
• Select(𝐴,𝑘)
If 𝐴 ≤5thensort𝐴andreturn𝑘thsmallest. Partition 𝑛 elements of 𝐴 into $* groups of size 5 each
Find median of each group by sorting the group 𝑀 ⟵ list of these medians
𝑠 ⟵ Select(𝑀, |,| ) )”
O(𝑛)
𝑇
𝑛 5
𝐴 ← sublist of 𝐴 with elements < 𝑠
𝐴- ← sublist of 𝐴 with elements > 𝑠
If 𝑘 < |𝐴)| + 1 then return Select(𝐴),𝑘)
If 𝑘 = |𝐴)| + 1 then return 𝑠
If 𝑘 > |𝐴)| + 1 then return Select(𝐴-,𝑘 − |𝐴)| − 1 )
O(𝑛)
𝑇
3𝑛
4
worst-caserunningtime𝑇 𝑛 =𝑇 $ +𝑇 #$ +𝑐𝑛
*
&
2021-01-13 CSC373 Winter 2021 – Sam Toueg 21
Worst-case running time 𝑇 𝑛 of Select(𝐴,𝑘) 𝑐𝑛 𝑛 3𝑛 𝑛 ≤ 5
𝑇𝑛=S𝑇5+𝑇4+𝑐𝑛 𝑛>5
• Claim:𝑇𝑛 =𝑂(𝑛)
• Proof:Weshow𝑇 𝑛 ≤20𝑐𝑛forall𝑛≥0
• By complete induction.
• Base case: for 𝑛 = 1,2,3,4,5. 𝑇 𝑛 ≤ 20𝑐𝑛, directly by the definition of 𝑇 𝑛
• Induction step: Let 𝑛 > 5.
• Suppose 𝑇 𝑚 ≤ 20𝑐𝑚 for all 𝑚 such that 0 ≤ 𝑚 < 𝑛 (Induction Hypothesis)
• Must show: 𝑇 𝑛 ≤ 20𝑐𝑛
• 𝑇 𝑛 =𝑇 . +𝑇 *. +𝑐𝑛 [bydefinitionof𝑇 𝑛 ] /+
Ø ≤ 20𝑐 . + 20𝑐 *. + 𝑐𝑛 [by the Induction Hypothesis] /+
Ø≤20𝑐 . +20𝑐 *. +𝑐𝑛 /+
Ø=4𝑐𝑛 +15𝑐𝑛+𝑐𝑛
Ø= 20𝑐𝑛
2021-01-13 CSC373 Winter 2021 - Sam Toueg 22
Why groups of 5?
• With groups of 5:
Ø Total size of subproblems: $ + %$ = "U$ < 𝑛
• With groups of 3:
Ø Total size of subproblems: $ + %$ = "%$ > 𝑛
• With groups of size 𝑥:
Ø Total size of subproblems:
ØWe want:
Ø T h i s h o l d s i f : V” + %2 < 1 ⇒ V" < "2 ⇒ 𝑥 > 4
• So group size 5 is ok and 7, 9, 11 would also work
• See handout in course web page for a proof!
2021-01-13 CSC373 Winter 2021 – Sam Toueg 23
T 2 #?
% 2 “#
$ + %$ V2
$ + %$ < 𝑛 V2
Divide & Conquer Closest Pair in R!
2021-01-13 CSC373 Winter 2021 - Sam Toueg 24
Overview and Motivation
• Problem:
ØInput: Set 𝑃 of 𝑛 points in the plane
ØOutput: Closest pair of points 𝑝 and 𝑞 in 𝑃 oi.e.,𝑑(𝑝,𝑞)≤𝑑(𝑝.,𝑞′),∀𝑝.,𝑞. ∈𝑃
𝑑 𝑝,𝑞 = (𝑥−𝑥′),+(𝑦−𝑦′),
𝑝 = (𝑥,𝑦)
𝑦 − 𝑦’ 𝑥 − 𝑥’
• Trivial Solution:
ØCompute the distance between every pair 𝑝, 𝑞 ∈ 𝑃
o O(𝑛")
2021-01-13 CSC373 Winter 2021 - Sam Toueg 25
q = (𝑥′, 𝑦′)
Closest Pair in 1D
3-Steps:
- Divide
- Conquer - Combine
𝜹𝑳
Recursively, find the closest pair here
𝜹 = 𝒎𝒊𝒏{𝜹𝑳 ,𝜹𝑪 ,𝜹𝑹}
𝜹𝑪 𝜹𝑹
Divide
Recursively, find the closest pair here
Conquer
Combine
Find the distance between the rightmost point on the left and the leftmost point on the right
𝑇 𝑛 =2·𝑇(𝑛/2)+c andtherefore𝑇 𝑛 =O(𝑛)
2021-01-13 CSC373 Winter 2021 - Sam Toueg 26
What if most points lie in 𝐵? We need to calculate Θ(𝑛,) distances!
Closest Pair in 2D
𝜹𝜹
𝜹 = 𝐦𝐢𝐧(𝜹𝐋, 𝜹𝐑)
𝛿3
𝒎
𝛿4
• •
L𝑩R
Divide: points in roughly equal halves by drawing a
vertical line to 𝑚
Conquer: Find the closest pair in each half, recursively
• Combine:Findtheclosestpair 𝑝,𝑞 , 𝑝∈𝐿and𝑞∈𝑅 2021-01-13 CSC373 Winter 2021 - Sam Toueg 27
Closest Pair in 2D
𝐵3 𝒎 𝐵4
𝜹 = 𝐦𝐢𝐧(𝜹𝐋, 𝜹𝐑)
𝑞
𝑝
𝜹
𝜹𝜹
B
Claim:Let𝑝=(𝑥8,𝑦8)∈𝐵kand𝑞= 𝑥9,𝑦9 ∈𝐵lwith𝑦8≤𝑦9. If 𝑑 𝑝,𝑞 < 𝛿 then there are at most six other points 𝑥,𝑦 in B
suchthat𝑦8 ≤𝑦≤𝑦9
2021-01-13 CSC373 Winter 2021 - Sam Toueg 29
Closest Pair in 2D
• Proof:
•𝑆b ={𝑝c =(𝑥,𝑦):𝑝c≠𝑝∈ 𝐵b 𝑎𝑛𝑑𝑦d ≤𝑦≤𝑦e}
•𝑆f ={𝑞c =(𝑥,𝑦):𝑞c≠𝑞∈ 𝐵f 𝑎𝑛𝑑𝑦d ≤𝑦≤𝑦e}
• Assume by contradiction that |𝑆b | ∪ 𝑆f •W.l.g.|𝑆b|≥4 𝐵3 𝒎 𝐵4
≥ 7
𝑞
𝑝
𝜹
𝜹𝜹
B
2021-01-13 CSC373 Winter 2021 - Sam Toueg
30
• Proof:
𝜹/𝟐
𝜹
𝜹/𝟐
𝐵3
𝒎
𝑺𝟏
𝑺𝟐
𝑺𝟑
𝑝
𝒖
𝒗𝑺𝟒
𝜹/𝟐
𝜹/𝟐
𝜹
• The 𝛿x𝛿 square has at least 4+1=5 points
• By PGP, one of the four (m#xm#) squares has at least 2 points 𝑢, 𝑣
• 𝑑 𝑢, 𝑣 ≤ m # + m # = m < 𝛿
# # # contradiction!
• But𝑢,𝑣∈𝐿and𝛿=min(𝛿k,𝛿l),so𝛿≤𝑑 𝑢,𝑣
2021-01-13 CSC373 Winter 2021 - Sam Toueg 31
We proved:
Let𝑝∈𝐵b and𝑞∈𝐵f .If𝑑 𝑝,𝑞 <𝛿thenthereareat most six other points in B (whose 𝑦-coordinates are)
between 𝑝 and 𝑞 𝜹
𝐵3
𝐵4
𝑞
𝑝
𝜹𝜹
B
So when the algo scans the nodes of B from bottom to top to find the pairs𝑝∈𝐵kand𝑞∈𝐵lwith𝑑𝑝,𝑞 <𝛿, foreachnode𝑝∈𝐵k algo has to look only at the next seven nodes ``up’’ from 𝑝 in B!
2021-01-13 CSC373 Winter 2021 - Sam Toueg 32
Closest Pair in 2D
𝐵3 𝐵4
𝜹 = 𝐦𝐢𝐧(𝜹𝐋, 𝜹𝐑)
𝛿3
𝒎
𝛿4
L𝜹𝜹R 𝑩
• Divide: points in roughly equal halves by drawing a vertical line to 𝑚
• Conquer: Find the closest pair in each half, recursively
• Combine: Find the closest pair 𝑝,𝑞 ,𝑝 ∈ 𝐵band 𝑞 ∈ 𝐵f
2021-01-13 CSC373 Winter 2021 - Sam Toueg 33
So𝑇 𝑛 =2·𝑇 𝑛/2 +𝑛·𝑐 andtherefore𝑇 𝑛 =O(𝑛log𝑛)
2021-01-13 CSC373 Winter 2021 - Sam Toueg 34
ClosestPair(𝑃)
# 𝑃 is a set of (at least 2) points on the plane, given by their 𝑥- and 𝑦-coordinates 𝑃7:= the list of points in 𝑃, sorted by 𝑥-coordinate
𝑃8:= the list of points in 𝑃, sorted by 𝑦-coordinate
return RCP(𝑃7,𝑃8)
RCP 𝑃7,𝑃8
# 𝑃7, 𝑃8 are lists of the same set of (at least 2) points, sorted by 𝑥- and 𝑦-coordinate, resp. if |𝑃7| ≤ 3 then calculate all pairwise distances and return closest pair
else
𝐿7 ∶= first half of 𝑃7; 𝑅7: = second half of 𝑃7
O(𝑛)
O(1)
2T(𝑛/2)
O(1)
O(𝑛) O(𝑛)
𝑚 ∶= (max 𝑥-coordinate in 𝐿7+ min 𝑥-coordinate in 𝑅7) / 2
𝐿8 ∶= sublist of 𝑃8 consisting of points in 𝐿7; 𝑅8 ∶= sublist of 𝑃8 consisting of points in 𝑅7
(𝑝𝐿, 𝑞𝐿) ∶= RCP(𝐿7, 𝐿8); (𝑝4, 𝑞4) ≔ RCP(𝑅7, 𝑅8)
O(𝑛)
O(1)
𝛿 ∶= min(𝑑(𝑝3, 𝑞3) , 𝑑(𝑝4, 𝑞4))
if 𝑑 𝑝3,𝑞3 = 𝛿 then 𝑝∗,𝑞∗ ∶= (𝑝3,𝑞3) else 𝑝∗,𝑞∗ ∶= (𝑝4,𝑞4)
𝐵 ∶= sublist of 𝑃8 consisting of points whose 𝑥-coordinates are within 𝛿 of 𝑚
for each 𝑝 in 𝐵 (in order of appearance in 𝐵) do
O(1)
for each of the next (up to) seven points 𝑞 after 𝑝 in 𝐵 do if 𝑑(𝑝, 𝑞) < 𝑑(𝑝∗, 𝑞∗) then (𝑝∗, 𝑞∗) ∶= (𝑝, 𝑞)
return (𝑝∗, 𝑞∗)