Computing convex hull by triangle point inclusion

Question

In my computational geometry book they present the following $O(n^4)$ algorithm for computing the convex hull of a pointset $P \subset \mathbb{R}^2$ assuming general position on the points in $P$: For all $O(n^3)$ triangles do an inclusion test for every point not yet discarded to see if they lie inside the triangle. If a point lies inside the current triangle discard it.

They mention that this can be improved to $O(n^2)$, but I fail to see how? The only $O(n^2)$ i can think of would be something like: Start at a point $P$ with maximum $y$-coordinate. Compute the angle to all other points in $P$ and choose the next point to be the point furthest to the left. Continue like so until you get to where you started, however this seems almost entirely unrelated to the triangle approach.

EDIT: I am aware of Jarvis march, Graham scan, Marriage before conquest etc, but my question is how specifically this idea of pruning points from triangles can yield a $O(n^2)$ algorithm for finding the convex hull

Answer 1

The authors could also mean Quick hull algorithm. It is based on discarding the points that lie inside a triangle. A naive implementation of the algorithm runs in $O(n^2)$ time.

Answer 2

The following algorithm may be what they mean:

Initialize $H\leftarrow \emptyset$.

For each point $p\in P$, test if $p$ lies inside the convex hull of $H$. If it does not lie inside the convex hull, add it to $H$.

After we have visited all points, $H$ will be the convex hull of $P$. Since we can test whether a point lies in a convex hull in $O(|H|)$, the algorithm runs in $O(n^2)$ time.