Chan`sAlgorithm

Report
Chan’s algorithm
CS504 Presentation
Planar Convex Hull
• Graham’s Scan : ( log )
• Jarvis’s March : (ℎ)
• Is there any ( log ℎ) algorithm?
CS504 Presentation
Chan’s Algorithm
• Chan’s algorithm
– combining Graham’s scan and Jarvis’s March together
–   log ℎ
• 3 stages of Chan’s algorithm
1.
2.
3.
divide vertices into partitions
apply Graham’s scan on each partition
apply Jarvis’s March on the small convex hull
(repeat 1~3 until we find the hull)
CS504 Presentation
Chan’s Algorithm
• Stage1 : Partition
• Consider arbitrary value  < , the size of partition
– how to decide  will be treated later
• Partition the points into groups, each of size 
– =


is the number of groups
CS504 Presentation
Chan’s Algorithm
• Stage 1
n = 32
Set m = 8
CS504 Presentation
Chan’s Algorithm
• Stage 1
n = 32
Set m = 8
r=4
CS504 Presentation
Chan’s Algorithm
• Stage2 : Graham’s Scan
• Compute convex hull of each partition using Graham’s
scan
• Total ( log ) time
CS504 Presentation
Chan’s Algorithm
• Stage 2
(After Stage 1)
m=8
r=4
CS504 Presentation
Chan’s Algorithm
• Stage 2
Using Graham’s Scan
O  log  for each group
-> total ( log )
= ( log )
CS504 Presentation
Chan’s Algorithm
• Stage3 : Jarvis’s March
• How to merge these r hulls into a single hull?
• IDEA : treat each hull as a “fat point” and run Jarvis’s
March!
• # of iteration is at most m
– to guarantee the time complexity O(nlogh)
CS504 Presentation
Chan’s Algorithm
• (-inf,0) -> lowest pt
(−∞, 0)
lowest pt
CS504 Presentation
Chan’s Algorithm
• Find the point that maximize the angle in each hull
(−∞, 0)
1
lowest pt
CS504 Presentation
Chan’s Algorithm
• Find the point that maximize the angle in each hull
(−∞, 0)
2
1
lowest pt
CS504 Presentation
Chan’s Algorithm
• Find the point that maximize the angle in each hull
3
(−∞, 0)
2
1
lowest pt
CS504 Presentation
Chan’s Algorithm
If  < ℎ, then the algorithm will fail!
CS504 Presentation
Chan’s Algorithm
• FAIL EXAMPLE – too small value m
m=4
(−∞, 0)
4 iteration
CS504 Presentation
Chan’s Algorithm
In 4(a), how to find such points?
CS504 Presentation
Chan’s Algorithm
• Find the point that maximize the angle in each hull
(−∞, 0)
1
lowest pt
CS504 Presentation
Chan’s Algorithm
• Find the point that maximize the angle in a hull
(−∞, 0)
CS504 Presentation
Chan’s Algorithm
• Finding tangent between a point and a convex -gon
5
1
 log  process
4
3
2
CS504 Presentation
Chan’s Algorithm
→ (log )
CS504 Presentation
Chan’s Algorithm
Analysis
• Suppose God told you some good value for 
– ℎ ≤  ≤ ℎ2
•   log  for stage1~2
• At most h steps in Jarvis’s March
– (log ) time to compute each tangent
–  tangent for each iteration

– total  ℎ log  = (ℎ  log ) time
• 
+ℎ


log  =   log  = ( log ℎ) as desired.
 ≤ ℎ2
CS504 Presentation
Chan’s Algorithm
• The only question remaining is…
how do we know what value to give to ?
CS504 Presentation
Chan’s Algorithm
• Answer : square search
• Try this way -  =

2
2, 4, 8, … , 2 , …
• Then we eventually get  to be in [ℎ, ℎ2 ] !
CS504 Presentation
Chan’s Algorithm
• The algorithm stops as soon as

2
2
≥ℎ
–  = lg lg ℎ
• Total time complexity
lg lg ℎ
lg lg ℎ
 log 2
=1
2
2 ≤  21+lg lg ℎ = 2 2lg lg ℎ
=
=1
= 2 log ℎ = ( log ℎ)
CS504 Presentation

similar documents