Lesson plan
Kirkpatrick–Seidel algorithm
The Kirkpatrick–Seidel algorithm is an algorithm designed for computing the convex hull of a set of points in the plane, offering a time complexity of \mathcal{O}(n \log h) , where n is the number of input points and h is the number of points on the convex hull. This output-sensitive time complexity implies that the algorithm’s running time depends on both the input size and the size of the output. Earlier output-sensitive algorithms, such as the gift wrapping algorithm, exhibited asymptotic running times of \mathcal{O}(n h) , while non-output-sensitive algorithms typically ran in \mathcal{O}(n \log n) time. The Kirkpatrick–Seidel algorithm offers a significant improvement by achieving a more efficient asymptotic bound, making it faster for certain types of input. Despite its theoretical optimality, the algorithm is not widely used in practice for moderate-sized data sets due to the implementation complexity and constants hidden in the asymptotic notation.
Article summary
The Kirkpatrick–Seidel algorithm is an algorithm designed for computing the convex hull of a set of points in the plane, offering a time complexity of \mathcal{O}(n \log h) , where n is the number of input points and h is the number of points on the convex hull. This output-sensitive time complexity implies that the algorithm’s running time depends on both the input size and the size of the output. Earlier output-sensitive algorithms, such as the gift wrapping algorithm, exhibited asymptotic running times of \mathcal{O}(n h) , while non-output-sensitive algorithms typically ran in \mathcal{O}(n \log n) time. The Kirkpatrick–Seidel algorithm offers a significant improvement by achieving a more efficient asymptotic bound, making it faster for certain types of input. Despite its theoretical optimality, the algorithm is not widely used in practice for moderate-sized data sets due to the implementation complexity and constants hidden in the asymptotic notation.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.