Chan's Algorithm to find Convex Hull

algorithm
computational-geometry
convex-hull
chan-algorithm

(Team) #1

Reading time: 35 minutes | Coding time: 15 minutes

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).


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