# 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.

• If I am right, you only need a first hull edge to start gift wrapping.
– user16034
Jan 5 at 9:37

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)$$.

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 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.

• 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$. Nov 26, 2018 at 5:44
• Please confirm that my updated algorithm works. Nov 26, 2018 at 8:11