3D gift wrapping algorithm: how to find the first face in the convex hull?

Question

I am implementing the gift wrapping algorithm to find the convex hull of a set of points in the 3D space.

However, all the articles I have read seem to omit the description of the first step of the algorithm; namely, finding a face (that is, a triangle) in the set that will definitely be in the convex hull (and doing so in $O(n^2)$).

Example of such an article: https://www.sciencedirect.com/science/article/pii/S002200000580056X

I do understand how to find a vertex that definitely be in the convex hull: just take one with extreme coordinates. However, I don’t know how to approach the problem for edges or faces.

Answer 1

Find a point with minimum $x$. $O(n)$.

Find the next vertex by 2D gift wrapping on the 2D projection of the points on a plane. $O(n)$.

The third vertex is obtained by comparing the faces built from the above edge and all remaining points. $O(n)$.

Answer 2

For simplicity, let us assume no four points are in the same plane. Otherwise, adapt the following procedure to deal with the degenerated cases.

Define the usual lexicographic order on points. That is, for any two distinct points $P$ and $Q$, $P<Q$ if the $x$ coordinate of $P$ is smaller than that of $Q$, or, if their $x$ coordinates are equal, the $y$ coordinate of $P$ is smaller than that of $Q$, or, if both x coordinates and y coordinates are equal, the $z$ coordinate of $P$ is smaller than that of $Q$.

Iterate through all points, keeping tracking of three smallest points. At the end of iteration, those three smallest points are the vertices of a triangle in the convex all.