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

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.

Define the usual lexicographic order on points. That is, for any two distinct points $$P$$ and $$Q$$, $$P 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$$.
• This doesn’t work. I am sorry for not being to provide details (this is an online judge problem), but: (1) $O(n^3)$ algorithm that just chooses $A$ with maximum $x$ coordinate and looks through all possible $B$s and $C$s, and then checks that the entire polyhedron is in one hemispace with respect to the plane induced by $ABC$, works; (2) if $B$ is not brute-forced but chosen as you said, it fails to find a face. Yes, no four points are coplanar, $n \ge 3$. – shdown Nov 26 '18 at 5:44