Convex Hull - Chan's Algorithm O(n log h) - Presentation by Yitian Huang and Zhe Yang

Convex Hull - Chan's Algorithm O(n log h) - Presentation by Yitian Huang and Zhe Yang

• 1.
  CONVEX HULL Yitian Huang& Zhe Yang Apr 22, 2016 1
• 2.
  Definition Of ConvexHULL Simply, given a set of points P in a plane, the convex hull of this set is the smallest convex polygon that contains all points of it. (A set of points and its convex hull) 2
• 3.
  We will introducean O(nlogh) algorithm known as Chan’s Algorithm, where h refers the number of points in the hull. However, Chan’s Algorithm is based on other two algorithms known as Jarvis’s Algorithm O(nh) and Graham’s Algorithm O(nlogn). So, we will talk about these two algorithms first. 3
• 4.
  Before Start… • Counterclockwiseand Clockwise • It’s relative • In this presentation • Use function orient(p, q, i) to calculate the relationship of pq and pi. • Obviously, orient(p, q, i) = - orient(p, i, q) • Extreme points • There will be four extreme points • All of them MUST be in the hull lastly • Most algorithm choose to start with one of the extreme points. • In this presentation • All algorithms will start will the left most point. 4
• 5.
  Jarvis’s Algorithm 5
• 6.
  Jarvis’s Algorithm • Perhapsthe simplest algorithm for computing Convex Hull • In the two-dimensional case the algorithm is also known as Jarvis march, after R. A. Jarvis, who published it in 1973. • It has a more visual name: ‘Gift Wrapping’. 6
• 7.
  HOW IT WORKS? 1.Start with the left most point, l. 2. Let p = l, find out the point q that appears to be furthest to the right to someone standing at p and looking at other points. (by comparing all others points) That’s is: orient(p, q, i) < 0 is always true for all other points. 3. Set q as p, and use p as the start point and use the same method to find the next q. 4. Keep doing step 3, until q is equal to l. O(n) O(h) Total: O(nh) O(n) 7
• 8.
  GRAHAM’S ALGORITHM 8
• 9.
  GRAHAM’S ALGORITHM • Itis named after Ronald Graham, who published the original algorithm in 1972. • Also know as Graham’s scan, first explicitly sorts the points and then scanning algorithm to finish building the hull. • Basically, sort + scan. 9
• 10.
  HOW IT WORKS? 1.Start with the left most point, l. 2. Sorts all other points in counterclockwise order around l. That’s is: orient(l, i, i+1) > 0 is always true for all points i. 3. Start with l, let p = l, q = l +1, i = l + 2. 4. Check orient(p, q, i) • If < 0, move forward, let p = q, q =i, i = i +1; • If > 0, remove q, let p = p-1, q = p ; 5. Keep doing step 4, until all points have been checked. O(nlogn) O(n) Total: O(nlogn) O(n) SORTSCAN 10
• 11.
  CHAN’S ALGORITHM 11
• 12.
  Chan’s Algorithm =Jarvis's + Graham’s + ... • It was discovered by Timothy Chan in 1993. • It’s a combination of divide-and-conquer, gift-wrapping and graham’s scan. • it’s output-sensitive, which means its running time depends on the size of its output (or input). 12
• 13.
  HOW IT WORKS? 1.Find a magic value of ‘m’, which divides all points into n/m subsets, and each subset has m points, approximately. 2. To each subset, use Graham’s algorithm to compute its sub-hull. 3. To all sub-hulls, use Jarvis’s algorithm to compute the final convex hull. • Choose one extreme point as the start point, and compare the right tangents of all sub-hulls. • Choose the rightest one as the next point. • Start with the next point, and do it again, until the next point is equal to the start point 13
• 14.
  Find Magic ‘m’ •The core of Chan’s algorithm is how to figure out the value of m. (The object is to make m very close to h, or equal) • Chan proposed a amazing trick here: • We set a parameter t = 1 and set m = 2^(2^t). • Then use this m to execute Chan’s Algorithm, in step 3, we set a counter for the output number of points in the hull. Once the counter reaches value m, it terminate the algorithm and increment t by 1, re-calculate the value m, and do it again! • By doing this, the time for running this algorithm will always be less than O(nlogm). 14
• 15.
  TIME COMPLEXITY • Wedivided points into n/m parts, so each part has m points. • Since the algorithm will be terminated when it number of output reaches m, so this step will at most cost O(nlogm), when m is small. • For step 2 • It’s O((n/m) * mlogm) = O(nlogm) • For step 3 • Finding one extreme point, O(n). • tangents • Finding the right tangents of one sub-hull, O(logm). • There are n/m sub-hulls, so O((n/m)logm) • There are h points in the hull. O(h*(n/m)logm) = O(nlogh) when h=m. • Totally, it’s O(nlogh). 1. Find a magic value of ‘m’, which divides all points into n/m subsets, and each subset has m points, approximately. 2. To each subset, use Graham’s algorithm to compute its sub-hull. 3. To all sub-hulls, use Jarvis’s algorithm to compute the final convex hull. • Choose one extreme point as the start point, and compare the right tangents of all sub-hulls. • Choose the rightest one as the next point. • Start with the next point, and do it again,until the next point is equal to the start point 15
• 16.
  16
• 17.
  REFERENCES • [1]. https://en.wikipedia.org/wiki/Chan%27s_algorithm •[2]. http://tomswitzer.net/2010/12/2d-convex-hulls-chans-algorithm/ • [3]. http://jeffe.cs.illinois.edu/teaching/373/notes/x05-convexhull.pdf • [4]. http://www.utdallas.edu/~daescu/convexhull.pdf • [5]. http://www.geeksforgeeks.org/convex-hull-set-1-jarviss-algorithm-or-wrapping/ • [6]. http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/ 17
• 18.
  THANK YOU! QUESTIONS? An examplefor Gift-wrapping NOT Chan’s Algorithm! 18