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.


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.

  • 1
    $\begingroup$ 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$. $\endgroup$
    – shdown
    Nov 26 '18 at 5:44
  • $\begingroup$ Please confirm that my updated algorithm works. $\endgroup$
    – John L.
    Nov 26 '18 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.