# Kirkpatrick–Seidel algorithm

> algorithm for computing the convex hull of a set of points in the plane in 𝒪(𝑛 log ℎ) time, where 𝑛 is the number of input points and ℎ is the number of points in the hull

**Wikidata**: [Q4060672](https://www.wikidata.org/wiki/Q4060672)  
**Wikipedia**: [English](https://en.wikipedia.org/wiki/Kirkpatrick–Seidel_algorithm)  
**Source**: https://4ort.xyz/entity/kirkpatrickseidel-algorithm

## Summary
The Kirkpatrick–Seidel algorithm is a method for computing the convex hull of a set of points in a plane. Its key feature is its average time complexity of 𝒪(𝑛 log ℎ), where 𝑛 is the number of input points and ℎ is the number of points in the final hull. This makes the algorithm's performance sensitive to the size of the output, offering an efficient solution for finding the smallest convex polygon that encloses all points.

## Key Facts
- **Classification**: An instance of a convex hull algorithm.
- **Time Complexity**: The average time complexity is 𝒪(𝑛 log ℎ).
- **Complexity Variables**: In its time complexity, `n` represents the number of input points, and `h` represents the number of points in the resulting convex hull.
- **Creators**: Named after computer scientists David G. Kirkpatrick and Raimund Seidel.
- **David G. Kirkpatrick**: A Canadian computer scientist and engineer, born in 1953.
- **Raimund Seidel**: An Austrian computer scientist, born in 1957.
- **Methodology**: A Russian alias for the algorithm translates to "Constructing a convex hull using the divide and conquer method," indicating its approach.

## FAQs
### Q: What is the time complexity of the Kirkpatrick–Seidel algorithm?
A: The algorithm has an average time complexity of 𝒪(𝑛 log ℎ). In this formula, 𝑛 is the total number of input points, and ℎ is the number of points that form the final convex hull.

### Q: Who created the Kirkpatrick–Seidel algorithm?
A: The algorithm is named after its creators, Canadian computer scientist David G. Kirkpatrick (b. 1953) and Austrian computer scientist Raimund Seidel (b. 1957).

### Q: What problem does the Kirkpatrick–Seidel algorithm solve?
A: It solves the problem of finding the convex hull for a set of points in a two-dimensional plane. The convex hull is the smallest convex polygon that contains all the given points.

## Why It Matters
The Kirkpatrick–Seidel algorithm's primary significance is its efficiency, which is formally described as "output-sensitive." Its time complexity, 𝒪(𝑛 log ℎ), depends not only on the number of input points (𝑛) but also on the number of points in the final hull (ℎ). This is a crucial advantage in common computational geometry scenarios where a very large set of points has a relatively simple convex hull (i.e., a small ℎ).

In such cases, the Kirkpatrick–Seidel algorithm can be significantly faster than other algorithms whose performance depends solely on the input size, such as those with a fixed 𝒪(𝑛 log 𝑛) complexity. By linking runtime to the output's complexity, the algorithm provides a more tailored and often superior solution for a fundamental problem in fields like computer graphics, data analysis, and robotics. Its design, which employs a divide-and-conquer strategy, represents an important development in the field of efficient geometric algorithms.

## Notable For
- **Output-Sensitive Complexity**: Its defining feature is the 𝒪(𝑛 log ℎ) time complexity, which makes its performance dependent on the size of the output hull (ℎ), not just the input point set (𝑛).
- **Divide and Conquer Strategy**: One of its aliases ("Построение выпуклой оболочки методом разделяй и властвуй") reveals that the algorithm is based on the "divide and conquer" paradigm, a fundamental technique in computer science.
- **Academic Naming**: The algorithm follows a common convention in computer science by being named directly after its two creators, David G. Kirkpatrick and Raimund Seidel.

## Body
### ### Definition and Purpose
The Kirkpatrick–Seidel algorithm is a computational method designed to solve the convex hull problem for a set of points in a two-dimensional plane. As a convex hull algorithm, its goal is to identify the smallest convex polygon that encloses all the points in the input set. The vertices of this polygon are a subset of the input points.

### ### Time Complexity
The algorithm is distinguished by its average time complexity, which is expressed as:
- **O(n log h)**

The variables in this expression are defined as:
- **n**: The total number of points in the input set.
- **h**: The number of vertices (points) that constitute the final convex hull.

Because the runtime depends on `h`, the size of the output, the algorithm is known as an output-sensitive algorithm. This makes it particularly efficient for point sets where `h` is much smaller than `n`.

### ### Creators
The algorithm is named after the two computer scientists who developed it:
- **David G. Kirkpatrick**: A Canadian computer scientist, engineer, and university teacher born in 1953.
- **Raimund Seidel**: An Austrian computer scientist born in 1957.