Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I already understood how the well-known algorithms like Graham, Quickhull etc. work, but i have difficulties in understanding 2 naive versions of convex hull algorithms:

Let S={p1, ..., pn} a set of points and CH(S) the convex hull of S.

("any_sentence" is a quote from different course books.)


A1) "find the smallest subset R ⊂ S for CH(R) = CH(S). Since there are 2n subsets, the complexity is O(2n)."
Well my question is: since we don't know CH(S) - and indeed it's our goal to achieve CH(S) - , how can we check if CH(R) == CH(S)? This makes no sense. Pseudocode version:

foreach (s in S.subsets)
    if (CH(R) == CH(S))
        return R

A2) "Let p,q,r,s ∈ S."
"s ∈ CH(S) if s is NOT ∈ triangle(p,q,r)"
And here is the algorithm:
enter image description here
My question: Is the first part of the sentence not wrong? According to my opinion, it should be: Let p,q,r ∈ CH(S) and s ∈ S. (But we would have the same problem again, i.e. that we don't know at the beginning what CH(S) is.) My counter example why this algorithm wouldn't work:
enter image description here
at the start we check the triangle(1,2,3) and see that 4 is not in the triangle, and mark 4 as not an element of convex hull, which is FALSE.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

A1) You're right, the algorithm description sounds kind of weird. A naive algorithm that takes exponential time would rather be something like

foreach (R in S.subsets)
  if (R.isConvexHull(S))
    return R

However, the method for checking whether R is a convex hull needs $n$ time, so we obtain a runtime of $n2^n$.

A2) Your premise is missing some quantifiers. I think, what you wanted to say is

"$\forall s, $ if $\forall p,q,r \in S, s \not \in \triangle(p,q,r),$ then $s$ is on the convex hull."

Furthermore, go through your example again. You understood it wrong. If you check triangle (1,2,3), you see that 4 is not in the triangle. Hence, 4 might still be on the convex hull (but it doesn't have to). On the contrary, if you check the triangle (4,3,2), you see that 1 is on the interior. Therefore, 1 is definitely not on the convex hull.

This still does not give you a convex hull algorithm though, since the points still have to be sorted by the end. However, this is no problem, since the rest of the algorithm already needs $\mathcal{O}(n^4)$ time.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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