Quick Hull Algorithm to find Convex Hull

algorithm
computational-geometry
quick-hull
convex-hull
divide-and-conquer
average-time-complexity-n-log-

(Team) #1

Reading time: 15 minutes | Coding time: 8 minutes

Quickhull is a method of computing the convex hull of a finite set of points in the plane. It uses a divide and conquer approach similar to that of quicksort, from which its name derives. Its average case complexity is considered to be Θ(n * log(n)), whereas in the worst case it takes O(n^2). Quick Hull was published by C. Barber and D. Dobkin in 1995.


This is a companion discussion topic for the original entry at http://iq.opengenus.org/quick-hull-convex-hull/