0
$\begingroup$

I already understood how the well-known algorithms like Graham's scan, Quickhull, etc. work, but I have difficulties in understanding 2 naive algorithms to compute the convex hull:

Let $S= \{p_1, \dots , p_n \}$ a set of points and $CH(S)$ the convex hull of $S$.


The first problem and corresponding algorithm are as follows.

Find the smallest subset $R \subset S$ for $CH(R) = CH(S)$. Since there are $2^n$ subsets, the complexity is $\mathcal{O}(2^n)$.

Pseudocode version:

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

Since we don't know $CH(S)$, and indeed it's our goal to compute $CH(S)$, how can we check if $CH(R) = CH(S)$?


The second problem is as follows.

Let $p,q,r,s \in S$. $s \in CH(S)$, if $s \not\in triangle(p,q,r)$

And here is the algorithm:

enter image description here

Shouldn't the first part of the sentence (of the problem) be

Let $p,q,r \in CH(S)$ and $s \in S$.

?

However, even in this case, we don't know what $CH(S)$ is.

My counterexample 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 the convex hull, but $4$ should be part of the CH!

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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