Chan's algorithm computes the convex hull of a set of points in O(n log h) time, where h is the number of points on the hull, combining the divide and conquer efficiency of algorithms like Quickhull with the output sensitivity of Jarvis march. It works by partitioning the points into small groups, computing each group's hull with a simple O(n log n) method, and merging the results using a gift wrapping style step whose group size is doubled across repeated guesses until the true hull size is found. Timothy Chan published the algorithm in 1996, and it is regarded as asymptotically optimal for the convex hull problem.
Facts
Time Complexity Classification
Design Technique Connections
Invented By
Timothy M. Chan published his optimal output-sensitive convex hull algorithm in 1996.
Sources
1. Wikipedia: Chan's algorithm
Lead section, naming sentence
named after Timothy M. Chan
Algorithm section, complexity sentence
The algorithm takes O(n log h) time, where h is the number of vertices of the output (the convex hull).
entity record, description (design-technique)
Chan's algorithm computes the convex hull of a set of points in O(n log h) time, where h is the number of points on the hull, combining the divide and conquer efficiency of algorithms like Quickhull with the output sensitivity of Jarvis march.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.