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