Divide and Conquer Hull Algorithm
<p>Hello my question today is to breakdown and figure out how to actually code the LOWER TANGENT part of the algorithm Ive managed to complete steps (1) and (2) but I am now on stuck on step (3).</p>

<p>Divide and Conquer Convex Hull </p>

<p>Hull(S) : </p>

<p>(1) If |S| &lt;= 3, then compute the convex hull by brute force in O(1)
time and return.</p>

<p>(2) Otherwise, partition the point set S into two sets A and B, where
A consists of half the points with the lowest x coordinates and B
consists of half of the points with the highest x coordinates.</p>

<p>(3) Recursively compute HA = Hull(A) and HB = Hull(B).</p>

<p>(4) Merge the two hulls into a common convex hull, H, by computing the
upper and lower tangents for HA and HB and discarding all the points
lying between these two tangents.</p>

<p><a href="http://www.cs.wustl.edu/~pless/506/l3_1.gif" rel="nofollow">http://www.cs.wustl.edu/~pless/506/l3_1.gif</a></p>

<p><strong>Finding the Lower Tangent</strong></p>

<p>LowerTangent(HA ; HB ) :</p>

<p>(1) Let a be the rightmost point of HA .</p>

<p>(2) Let b be the leftmost point of HB .</p>

<p>(3) While ab is not a lower tangent for HA and HB do</p>

<p>(a) While ab is not a lower tangent to HA do a = a - 1 (move a clockwise).</p>

<p>(b) While ab is not a lower tangent to HB do b = b + 1 (move b counterclockwise).</p>

<p>(4) Return ab.</p>

<p>Quoted from: <a href="http://www.cs.wustl.edu/~pless/506/l3.html" rel="nofollow">http://www.cs.wustl.edu/~pless/506/l3.html</a>
This explanation is the best that describe my problem.</p>

<p>The functions for Lexisort and convexHull have not been included as they are working, the DC hull algorithm has been included to provide context.</p>

<p>My current code:</p>

<pre><code>public static int [][] dcHull(int [][]merged){

    if(merged.length &lt;= 3)
        return convexHull(merged);

    else {

        lexiSort(merged);
        //split(P, A, B);
        //SPLIT
        double p = merged.length;
        int A;
        int B;

        if (p%2 == 0){//EVEN
            A = (int) (p/2);
            B = (int) (p/2);
        }
        else//ODD
            A = (int) (1+(p/2));
            B = (int) (p/2);



        int arrayA[][] = new int[A][2]; 
        int arrayB[][] = new int[B][2];

        for (int i=0; i&lt;A; i++){
            arrayA[i][0] = merged[i][0];
            arrayA[i][1] = merged[i][1];
        }

        for (int i=0; i&lt;B; i++){
            arrayB[i][0] = merged[i+A][0];
            arrayB[i][1] = merged[i+A][1];
        }

        for ( int i=0; i&lt;arrayA.length; i++){
            System.out.println( "Merged array A Coordinates: " + arrayA[i][0] +", " + arrayA[i][1]);}
        for ( int i=0; i&lt;arrayB.length; i++){
            System.out.println( "Merged array B Coordinates: " + arrayB[i][0] +", " + arrayB[i][1]);}

        lowerT(arrayA, arrayB);
        //upperT(arrayA, arrayB);


        return merged(dcHull(convexHull(arrayA)), dcHull(convexHull(arrayB)));

    }

}

public static int[][] lowerT(int [][] hulla, int [][]  hullb){

    int a = 0;
    int b = 0;

    //LOWER TANGENT
    //(1) Let a be the rightmost point of HA .
    for (int i=0; i&lt;hulla.length; i++){
        if (a &lt; hulla[i][0]){
            a = hulla[i][0];
        }
    }
    //(2) Let b be the leftmost point of HB .
    for (int i=0; i&lt;hullb.length; i++){
        if (b &lt; hullb[i][0]){
            b = hullb[i][0];
        }
    }
    for (int i=0; i&lt;hullb.length; i++){
        if (b &gt; hullb[i][0]){
            b = hullb[i][0];
        }
    }
</code></pre>

<p>The code finishes after working out a of HA and b of HB however I do not understand (3) or more precisely how to code it using the elements I have. </p>

<p>(1) Let a be the rightmost point of HA .</p>

<p>(2) Let b be the leftmost point of HB .</p>

<p>There is an additional method of code called right turn that I believe is useful:
"Lower tangency is a condition that can be
tested locally by an orientation test of the two vertices and
neighboring vertices on the hull."</p>

<p>Im just not sure how to put it together.</p>

<pre><code>public static boolean rightTurn(int [][] rt, int counter) //AxBxC = (Bx-Ax)(Cy-Ay)-(By-Ay)(Cx-Ax)
{
    int ax = rt[counter-2][0];
    int bx = rt[counter-1][0];
    int cx = rt[counter][0];

    int ay = rt[counter-2][1];
    int by = rt[counter-1][1];
    int cy = rt[counter-0][1];
    int result =(bx-ax)*(cy-ay)-(by-ay)*(cx-ax);

    if (result &lt; 0){                            // Result = VE+ (Right Turn), 0, VE- (Left Turn)

        return true;                                                    //VE- = TRUE = Right Turn
    }

    else return false;                                                  //VE+ = FALSE = Left Turn
}
</code></pre>
