Is there any convex hull algorithm that can be extended to non-euclidean metric, such as the geodesic distance on the surface of a sphere?


I'm not sure what metrics have to do with it: convexity is about barycentric coordinates rather than distance.

The surface of the sphere is nasty because of antipodes. Roughly speaking, if there is an open hemisphere which contains all of the input points, you can work in that hemisphere without problems. Otherwise, the convex hull is going to be the entire surface.

Supposing that there is an open hemisphere containing the points, essentially any 3D convex hull algorithm will work by the addition of an extra point at infinity. But it's probably more elegant to take the centroid in $\mathbb{R}^3$, project to the surface, and use it as a centre around which to apply your favourite wrapping algorithm.

  • $\begingroup$ Can you explain why the convex hull is the entire surface if the points don't lie in a hemisphere? $\endgroup$
    – user7868
    Jan 27 at 3:40

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.