Graham Scan Algorithm
source link: https://www.geeksforgeeks.org/videos/graham-scan-algorithm/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Graham Scan Algorithm
- 13/06/2022
We have discussed Jarvis’s Algorithm for Convex Hull. The worst case time complexity of Jarvis’s Algorithm is O(n^2). Using Graham’s scan algorithm, we can find Convex Hull in O(nLogn) time. Following is Graham’s algorithm Let points[0..n-1] be the input array. 1) Find the bottom-most point by comparing y coordinate of all points. If there are two points with the same y value, then the point with smaller x coordinate value is considered. Let the bottom-most point be P0. Put P0 at first position in output hull. 2) Consider the remaining n-1 points and sort them by polar angle in counterclockwise order around points[0]. If the polar angle of two points is the same, then put the nearest point first.
Graham Scan Algorithm : https://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK