4
$\begingroup$

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.

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

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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