CS计算机代考程序代写 algorithm Divide & Conquer Order Statistics

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 (𝑝∗, 𝑞∗)