# 3D Convex Hull Divide and Conquer Advancing Mechanism

I am currently trying to implement the divide and conquer method of computing the 3D convex hull given by Preparata, outlined here:

http://www.cs.jhu.edu/~misha/Spring14/Preparata77.pdf

The convex hull CH(A, B) of A and B may be obtained by the following operations (see Figure 4 for an intuitive illustration):

(1) Construction of a "cylindrical" triangulation $\Im$, which is tangent to A and B along two circuits $E_{A}$ and $E_{B}$, respectively.

(2) Removal both from A and from B of the respective portions which have been "obscured" by $\Im$.

Here is where the paper describes the construction of the "cylindrical" triangulation.

We now describe the advancing mechanism of the procedure. If we temporarily exclude degeneracies, i.e. we assume that each face of $\Im$ is a triangle, each step determines a new vertex, whereby a new face is added to $\Im$. We shall discuss later the case in which the restriction on degeneracies is removed. In our illustration (Figure 4), $a_{2}$ and ($a_{2}$, $b_{2}$, $a_{1}$) are, respectively, the vertex and the face of $\Im$ constructed in the previous step. The advancing mechanism makes reference to the most recently constructed face of $\Im$. To initialize the procedure, the reference face is chosen as one of the half planes parallel to the $x_{3}$ axis, containing the initially determined edge and delimited by it. Let ($a_{2}$, $b_{2}$, $a_{1}$) be the reference face for the current step. We must now select a vertex $\hat{a}$, connected to $a_{2}$, such that the face ($a_{2}$, $b_{2}$, $\hat{a}$) forms the largest convex angle with ($a_{2}$, $b_{2}$, $a_{1}$) among the faces ($a_{2}$, $b_{2}$, v), for all v $\neq$ $a_{1}$ connected to $a_{2}$ ; similarly we select $\hat{b}$ among the vertices connected to $b_{2}$. For reasons to become apparent later, we call these comparisons of type 1.

Next, once the "winners" ($a_{2}$, $b_{2}$, $\hat{a}$) and ($a_{2}$, $b_{2}$, $\hat{b}$) have been selected, we have a run-off comparison, called of type 2. If ($a_{2}$, $b_{2}$, $\hat{a}$) forms with ($a_{2}$, $b_{2}$, $a_{1}$) a larger convex angle than ($a_{2}$, $b_{2}$, $\hat{b}$), then $\hat{a}$ is added to $\Im$ ($\hat{b}$ is added in the opposite case) and the step is complete.

My question is how do you determine the vertices of the new triangle after you have chosen the winner?

• Can you edit your question add the full citation to the paper, so that if the link dies, readers will still be able to know what paper you are referring to? Thank you! – D.W. Aug 10 '15 at 3:15