http://cs.jhu.edu/~misha/Spring14/Preparata77.pdf
This is a divide and conquer algorithm for computing the convex hull in 3 dimensions.
I am having trouble understanding the merge step, which is titled Merge in 3 Dimensions, outlined in the paper.
I am specifically having trouble understanding how the number of comparisons made is done in O(n) time for the whole hull.
On page 92 in the last paragraph on the left column, it says that the number of comparisons made is bounded by the number of edges which is linear for each hull. But what if each vertex had p edges (so you are checking duplicates), then that would add up to quadratic running time. Or, if the number of edges each time was monotonically increasing from 1 to p-1, that still adds up to quadratic running time for the comparisons. For instance, a tetrahedron has 4 vertices and each vertex has a degree of 3, so the number of comparisons made would be 12.