Chan's Algorithm to find Convex Hull


(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