Chan's Algorithm to find Convex Hull
In computational geometry, Chan's algorithm, named after Timothy M. Chan, is an optimal output-sensitive algorithm to compute the convex hull of a set P of n points, in 2- or 3-dimensional space. The algorithm takes O(n log h) time, where h is the number of vertices of the output (the convex hull).
Graham Scan Algorithm to find Convex Hull
Graham's Scan Algorithm is an efficient algorithm for finding the convex hull of a finite set of points in the plane with time complexity O(N log N). The algorithm finds all vertices of the convex hull ordered along its boundary. It uses a stack to detect and remove concavities in the boundary.
Gift Wrap Algorithm (Jarvis March Algorithm) to find Convex Hull
Gift Wrap Algorithm ( Jarvis March Algorithm ) to find the convex hull of any given set of points. We start from the leftmost point (or point with minimum x coordinate value) and we keep wrapping points in a counterclockwise direction. Find pseudocode, implementations, complexity and questions
Divide and Conquer algorithm to find Convex Hull
Divide and Conquer algorithm to find Convex Hull. The key idea is that is we have two convex hull then, they can be merged in linear time to get a convex hull of a larger set of points. It requires to find upper and lower tangent to the right and left convex hulls C1 and C2