1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What specifically are you confused about? Are you confused how it works? Confused about why it produces the correct answer? About the running time analysis? What have you done to try to understand? What step/sentence in the explanation is the first one that you don't understand? $\endgroup$
    – D.W. ♦
    Jul 15, 2015 at 22:31
  • $\begingroup$ It looks like you have two accounts with the same name. I think you can get them linked together if you ask the mods (or maybethe site admins). $\endgroup$
    – David Richerby
    Jul 17, 2015 at 8:14
  • $\begingroup$ To merge two accounts, follow the procedure listed here: cs.stackexchange.com/help/merging-accounts $\endgroup$
    – D.W. ♦
    Jul 18, 2015 at 1:20

1 Answer 1

Reset to default
2
$\begingroup$

The paper explains why the number of comparisons is $O(n)$ in the next few sentences immediately after the statement you're asking for a justification of. Just keep reading for a few more sentences, and you'll immediately find the justification. As it says,

"First of all, we notice that each type 1 comparison definitively eliminates one edge ... Since the numbers of edges of A and B are at most $(3p-6)$ and $(3q-6)$, respectively, the number of type 1 comparisons is bounded by ..."

and so on. So to find the explanation for that statement, just continue reading a few sentences onward.

And, as the paper says in the introduction,

"[our algorithm]" is based on the property that the number of edges of the convex hull of $n$ points is at most linear in $n$."

Therefore, your examples are not possible.

See also the 3rd paragraph of Section 4 for more elaboration ("It is a crucial observation that...").

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.