Understanding a few intricacies related to two naive algorithms to compute the convex hull of a set of points

Question

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:

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:

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!

Answer 1

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.