Implementation issues on the marriage before conquest convex hull algorithm

Question

I'm interested in implementing and studying the Kirkpatrick–Seidel algorithm. It's a divide and conquer approach of finding the convex hull of some set of points. I care only about the 2 dimensional case.

I found an interesting handout about this problem here:

The general steps of the algorithm are as follows:

  INPUT: A set P of points on the plane.
  OUTPUT: The set of points that define the convex hull.
  1. Calculate median x-coordinate M of P. 
  2. Find the bridge segment that crosses the line x = M using the 
     Prune and Search Technique.
  3. Trim the set based on this segment
  4. Split P to sets PL, PR and recursively apply the above steps to find
     the remaining segments
  5. The above steps must be run twice, once for the upper hall and once
     for the lower hall. Once you find both, you have the convex hull.

(1) can be found in O(N). It's very trivial, especially in C++ you can just use nth_element with a specified comparator

(3) can also be found in O(N). If the segment that you found is defined by points p1 and p2 then you just need to ignore each point p where p1.x <= p.x <= p2.x

(4) is just the direct result of (3)

(5) two recursive calls on the two subsets that you just found

In order to achieve the O(nlogn) complexity from this divide and conquer algorithm. We need step (2) to also take O(n).

According to the handout, this step can be solved with linear programming and since we are working on the plane, linear time can be achieved.

Now, the handout goes to explain part (2) in more detail, here are the steps.

enter image description here

I understand every step except (3) and (4).

(3). What is b? I guess it doesn't matter. Since you have found the slope m and then proceed to find the supporting line for set P. B is something that you are looking for.

(4). what is the supporting line for set P and how to find it efficiently?

David Eisenstat David Eisenstat · Accepted Answer · 2014-10-05T00:44:51

Given a slope and a point, there exists a unique line with that slope through that point. Let the slope be m and the point be (px, py). Then solve for b in the equation py = m px + b (i.e., b = py - m px); the line has the equation y = m x + b. What you're supposed to do in steps (3) and (4) is to compute b for each point and take p_t to be the point having maximum b (breaking ties by maximum x-coordinate). This line is a supporting line of the convex hull because it contains one of the vertices and has all of the vertices (improperly) to one side (in this case, not above it).

_{P.S. If you're interested because of the O(n log h) running time, then don't get your hopes up; the constant factor looks pretty bad.}

Implementation issues on the marriage before conquest convex hull algorithm

1 Answers