Kirkpatrick-Seidel Algorithm (Ultimate Planar Convex Hull Algorithm)

Reading time: 15 minutes | Coding time: 9 minutes

Algorithm

Kirkpatrick and Seidel presented an algorithm that reverses the idea of divide-and-conquer, into a concept they dubbed marriage before-conquest . Normally, a divide-and-conquer algorithm wouldsplit the input, recursively perform a set of operations on each part,and merge the parts. The marriage-before-conquest 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 x-coordinate 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 ∈ S|x(p) < x($p_i$)}
• $S_{right}$ ← pj ∪ {p ∈ S|x(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 output-sensitive, 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 y-coordinate to candidates.
    • Remove pair from pairs.
  • end if
• 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 x-coordinate.
• $p_m$ ← the point in max with maximum x-coordinate
• 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$)

Download pdf for more details

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 three-dimensional box surrounding an object depends on the 3D-convex 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 computational-geometric algorithms such as the rotating calipers method for computing the width and diameter of a point set.