[Solved]: naive convex hull algorithms

Problem Detail: 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:

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:

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.

Asked By : Schwammkopf

Answered By : HdM

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/8944 Ask a Question Download Related Notes/Documents