# Algorithm for Calculating Spheric Convex Hulls of Finite Pointsets

Let the Spheric Convex Hull ($$\mathrm{CH}_S$$) denote the intersection of all closed spheres that contain a compact $$\Sigma\subset\mathbb{R}^n$$ and on their boundary at least $$n+1$$ distinct points of $$\Sigma$$

Question:

how can the cell structure of $$\mathrm{CH}_S(\Sigma)$$ be efficiently determined from the cell structure of $$\mathrm{CH}(\Sigma)$$ in case $$\quad n+1\ \le\ \partial\mathrm{CH}(\Sigma)\cap\Sigma\ \lt\ \infty,\quad \Sigma\subset\mathbb{R}^n\$$, when $$\mathrm{CH}$$ denotes the standard convex hull and $$\partial\mathrm{CH}$$ the set of its boundary points?

An example that shows that the cell structures actually can be different:
take the corners of triangle plus three further points, one to each side of the triangle and slightly outside the circum circle. The cell structure of $$\partial\mathrm{CH}$$ contains 6 line segments, whereas $$\mathrm{CH}_S$$ contains only three circular arcs.

The bigger red dots mark the delimiters of the circular arcs of $$\mathrm{CH}_S$$

Edit
just realized, the spheres that contribute $$\mathrm{CH}_S$$ can be characterized as follows: after a stereographic projection of $$\Sigma$$ onto the unit sphere of appropriate dimension the contributing hyperspheres correspond to hyperplanes through $$n+1$$ stereo-projected points that separate the origin from the projected points that are not on that hyperplane; maybe that observation simplifies matters.

• Are not the cell structures identical? For spheres with very large radii through the corners of a triangle face of the hull will approach halfplanes tangent to that triangle. For finite pointsets, the limit as the radii go to $\infty$ is the regular convex hull. – Joseph O'Rourke Feb 3 at 14:03
• @JosephO'Rourke yes you are right; I will edit my question and add an important restriction, that makes the cell structures possibly different – Manfred Weis Feb 3 at 14:33
• Note that the spherical hull of $n+1$ general-position points in $\mathbb{R}^n$ is in fact a sphere. – Joseph O'Rourke Feb 3 at 15:52
• @JosephO'Rourke yes, that is the degenerate case; thanks for mentioning it. I wrote "at least n+1" to not rule out that case. – Manfred Weis Feb 3 at 16:00