Visualizing the Ultimate Convex Hull Algorithm

About the Algorithm

The Kirkpatrick–Seidel algorithm, also known as "the Ultimate Planar Convex Hull Algorithm (?)," is an algorithm for computing the convex hull of a set of points in the plane. It is a particularly notable because it can compute the convex hull of $n$ points in $O(n \log h)$ time, where $h$ is the number of points in the hull.

Unlike other comparable $O(n \log h)$ algorithms that combine and tweak other convex hull algorithms, the Ultimate Convex Hull Algorithm is a divide-and-conquer algorithm that then uses bridges to merge our problem.

If you're interested in exploring the algorithm, add some points to the canvas below and see how it works!

Reference Material

If you're looking for some material to review the terminology and concepts of algorithms and computational geometry, check out the following resources:

• Big-O Notation and Time Complexity
• Basics of Convex Hull
• A Few Simpler CH Algorithms

If you're looking for further reading on Kirkpatrick–Seidel's algorithm (or other comparable methods), check out these links:

• Kirkpatrick–Seidel Algorithm on Wikipedia
• Kirkpatrick and Seidel's original paper
• An extension of the Kirkpatrick-Seidel algorithm in O(n) time (note: not verified)
• Chan's Algorithm (a comparable algorithm)
• A visual explanation of Chan's Algorithm