KirkpatrickSeidel Algorithm (Ultimate Planar Convex Hull Algorithm)
Get this book > Problems on Array: For Interviews and Competitive Programming
Reading time: 15 minutes  Coding time: 9 minutes
The Kirkpatrick–Seidel algorithm, called by its authors "the ultimate planar convex hull algorithm", is an algorithm for computing the convex hull of a set of points in the plane, with O( N log H) time complexity, where N is the number of input points and H is the number of points (non dominated or maximal points, as called in some texts) in the hull. Thus, the algorithm is outputsensitive: its running time depends on both the input size and the output size. Another outputsensitive algorithm, the gift wrapping algorithm, was known much earlier, but the Kirkpatrick–Seidel algorithm has an asymptotic running time that is significantly smaller and that always improves on the O( N log N) bounds of nonoutputsensitive algorithms. The Kirkpatrick–Seidel algorithm is named after its inventors, David G. Kirkpatrick and Raimund Seidel.
Algorithm
Kirkpatrick and Seidel presented an algorithm that reverses the idea of divideandconquer, into a concept they dubbed marriage beforeconquest . Normally, a divideandconquer algorithm wouldsplit the input, recursively perform a set of operations on each part,and merge the parts. The marriagebeforeconquest algorithm splits the input, and instead of just recursing on each set, the algorithm first figures out how the parts should be merged, and then recurses on the subsets. This algorithm only focuses on finding the upper part of the convex hull, but the lower hull can be found by flipping or rotating all points. These hulls can then be concatenated to form the complete convex hull.
GiftWrapHull(S)
 L = ∅
 min ← min(S)
 L.add(min)
 direction ← (0, 1)
 while next != L.last do
 nextPoint = ∅
 smallestAngle = ∞
 for all p : points do
 angle ← angle(direction, p)
 if angle < smallestAngle then
 smallestAngle ← angle
 nextPoint = p
 end if
 end for
 L.add(nextPoint)
 end while
The algorithm works by finding a vertical line $x_m$ through the median xcoordinate of the input points S. It then finds the bridge through $x_m$, that is, the edge of the upper hull crossing $x_m$, seen in figure , where $x_m$ is called L. As per the definition of a convex hull, all vertices beneath this bridge can not be a part of the upper hull, and they are pruned from the set. The remaining points are split into two sets, $S_{left}$ and $S_{right}$, containing the points to the left and right of this bridge. The points in the bridge are added to the hull and the
algorithm is called recursively on each subset.
Finding the bridge
The main idea when looking for a bridge is pruning points from the set $S$, until only the two points forming the bridge remain. To do this, it divides $S$ into $S/2$ pairs, and calculates the slopes of the lines intersecting the points from each pair. It then finds the median $K$ of these slopes, approximated by picking the median of one or more slopes at random, and separates all the pairs into three groups: those with a higher slope than $K$, those with a lower slope, and those with the same slope. The line with slope K is then moved up, to where it hits the top points, maximizing $p_y − Kp_x$, while keeping track of the minimum and maximum point on this line. If there are more than one point on the line, and the points are on different sides of $x_m$, the minimum and maximum points form the bridge, and they are returned. If there is only one point on the line, it lies either to the left, on, or to the right of $x_m$. Based on the relation between the sets, $K$, and on which side of xm the points lie, up to one point from each pair may be pruned. This runs recursively until only one point on each side of $x_m$ remains. Pseudocode for this subroutine can be seen in algorithm.
KirkpatrickSeidelHull(S)
 $x_m$ ← median(x)
 (i, j) ← Bridge(S, $x_m$)
 $S_{left}$ ← $p_i$ ∪ {p ∈ Sx(p) < x($p_i$)}
 $S_{right}$ ← pj ∪ {p ∈ Sx(p) > x($p_j$)}
 if i = min(S) then
 print i
 else
 KSHull($S_{left}$)
 end if
 if j = max(S) then
 print j
 else
 KSHull($S_{right}$)
 end if
This algorithm is outputsensitive, in that the running time depends on both the size of the input and the size of the computed hull.
For finding the median, randomized selection is used, as it will give a reasonable approximation of the real median. It is also assumed that the bridge finding algorithm runs on O(n) time. The running time of the function is determined by
f(S , h) where f must satisfy the following recurrence relation:
Bridge(S, $x_m$)
 candidates ← ∅
 if S = 2 then
 return (i, j), where S = {$p_i,p_j$} and $x(p_i) < x(p_j)$
 pairs ← j $[S/2]$ disjoint pairs of points from S, ordered by xcoordinate.
 if S is uneven then
 Add unpaired point to pairs.
 end if
 Calculate slope for all pairs.
 for all pairs in pairs do
 if Any slopes are vertical then
 Add point with highest ycoordinate to candidates.
 Remove pair from pairs.
 end if
 if Any slopes are vertical then
 end for
 K ← median of slopes
 small ← pairs with slope < K.
 equal ← pairs with slope = K.
 large ← pairs with slope > K.
 max ← the set of points on the line maximizing y($p_i$) − x($p_i$)K
 $p_k$ ← the point in max with minimum xcoordinate.
 $p_m$ ← the point in max with maximum xcoordinate
 if x($p_k$) ≤ $x_m$ and x($p_m$) > $x_m$ then
 ($p_k$,$p_m$) is the bridge, return (k, m).
 end if
 if x($p_m$) ≤ $x_m$ then
 Insert right point from all pairs in large ∪ equal into candidates
 Insert both points from all pairs in small into candidates
 end if
 if x($p_k$) > $x_m$ then
 Insert left point from all pairs in small ∪ equal into candidates
 Insert both points from all pairs in large into candidates
*end if
 return Bridge(candidates, $x_m$)
Complexity
 The complexity of algorithm is O(n logh) where where n is the number of input points and h is the number of points (non dominated or maximal points, as called in some texts) in the hull.
 It is output sensitive algorithm.
Applications
The applications of this Divide and Conquer approach towards Convex Hull is as follows:
 Collision avoidance: If the convex hull of a car avoids collision with obstacles then so does the car. Since the computation of paths that avoid collision is much easier with a convex car, then it is often used to plan paths.

Smallest box: The smallest area rectangle that encloses a polygon has at least one side flush with the convex hull of the polygon, and so the hull is computed at the first step of minimum rectangle algorithms. Similarly, finding the smallest threedimensional box surrounding an object depends on the 3Dconvex hull.

Shape analysis: Shapes may be classified for the purposes of matching by their "convex deficiency trees", structures that depend for their computation on convex hulls.

Other practical applications are pattern recognition, image processing, statistics, geographic information system, game theory, construction of phase diagrams, and static code analysis by abstract interpretation.

It also serves as a tool, a building block for a of other computationalgeometric algorithms such as the rotating calipers method for computing the width and diameter of a point set.