I have $n$ points $p_1,...,p_n\in\mathbb{R}^3$, $\|p_i\|=1$, which define a contour on a unit sphere. We are guaranteed that the contour has no self-intersections and all the points can be fit on one semi-sphere. The latter ensures that we can adequately determine the direction of the contour: clockwise (CW) or counterclockwise (CСW). Is there a way to develop a linear procedure for that? The main obstacle here is that the contour is on a sphere, whereas on a plane the problem can be solved with help of consequent vector products.
My idea was to find a plane that would cut the sphere into two semi-spheres, such that all points appear exclusively on one of the semi-spheres. Then project all points onto this plane and solve the problem in 2d case. But I couldn't figure out how to find such plane given $p_1,...,p_n$.
Any help, suggestions or nudges to the right direction would be greatly appreciated!
I'm going to talk about geometry on a sphere, and use words like "segment" and "convex hull". I'm goign to assume you can make sense of these. For instance, the segment between two distinct non-antipodal points $P$ and $Q$ is the shorter of the two arcs of the great circle containing $P$ and $Q$.
NB: I'm assuming that "within" a hemisphere means in the interior of a hemisphere, not on the boundary, for if boundary points were allowed, our set could consist of 3 evenly spaced points on the equator, and then clockwise/counterCW can't be determined.
Lemma: Given a set $P$ of points in a hemisphere $H$, we can compute the convex hull of $P$ as an ordered subset of $P$ defining the oriented boundary of the convex hull.
Proof: The hemisphere $H$ is defined by an equation of the form $n \cdot x \ge 0$ for some fixed vector $n$. We can rotate the sphere so that $-n$ is the vector $(0,0, -1)$, and then each point $p$ will have positive $z$ coordinate. Project from the sphere center onto the plane $z = 1$ via $(x, y, z) \mapsto (\frac{x}{z}, \frac{y}{z}, 1)$ to get points $q_i$ from the input points $p_i$. Compute the convex hull of the $q_i$ in the $z = 1$ plane using conventional methods (e.g. linear-time Graham scan), and then project back to get a convex hull for the $p_i$.
Lemma: if the points $p_i$ ($i = 1, \ldots, n$) lie in the intersection of two hemispheres $H_1$ and $H_2$ whose normal-vectors have positive dot-product and we compute the vertices of the convex hull of the $p_i$ using these hemispheres, the results are the same.
Proof: The map from the $z=1$ plane in one computation to the $z = 1$ plane in the other computation (in the previous lemma) is a fractional linear transformation of positive determinant. And I think that's enough to prove this lemma, but I can't really promise that without some more work.
Main algorithm:
find a point $q$ (e.g., any interior point of the arc from $p_1$ to $p_2$ that's NOT one of the $p_i$) that's in the hemisphere containing the $p_i$s. Find a plane through $q$ that divides the input points approximately in half, but does not contain any of them. Each of the two piles of input points now lies in a hemisphere, so we can find its convex hull. "merge" these (as in the Preparata convex hull algorithm) to find the convex hull of the whole.
Now that's all just a kind of vague sketch, I admit. But I think it might get you where you want to go if you work out all the details.