patternMinor
Convex Hull on a Spherical Surface
Viewed 0 times
convexsphericalsurfacehull
Problem
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#12405, answer score: 2
Revisions (0)
No revisions yet.