- This video explains the convex hull problem well and goes through the two simple algorithms.
- Here's the Wiki
There are several different algorithms for solving the problem.
- Detailed here the Naive Approach is basically an
$O(n^3)$ algorithm
- Starts at a point that is definitely in the convex hull (point farthest in a certain direction).
- Choosing points at random the point is selected that makes the most "outward" angle.
- Marching on with that point, the process repeats, circling around the entire hull.
Explained in this video, Grahm's scan improves on the Jarvis March by
- ordering the verticies by angle from starting point.
This makes the algorithms$O(n \log n)$ .
- Covered in this paper are some more optimal solutions.
- There is also the Akl–Toussaint heuristic that should speed things up for any of these algorithms. I plan to have this as an optional addition to my algorithms.
- I'm thinking of implementing the Kirkpatrick-Seidel optimal solution too.