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$


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.

Illustration of the difference of the cell structures

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

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.

  • $\begingroup$ 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. $\endgroup$ – Joseph O'Rourke Feb 3 at 14:03
  • $\begingroup$ @JosephO'Rourke yes you are right; I will edit my question and add an important restriction, that makes the cell structures possibly different $\endgroup$ – Manfred Weis Feb 3 at 14:33
  • $\begingroup$ Note that the spherical hull of $n+1$ general-position points in $\mathbb{R}^n$ is in fact a sphere. $\endgroup$ – Joseph O'Rourke Feb 3 at 15:52
  • $\begingroup$ @JosephO'Rourke yes, that is the degenerate case; thanks for mentioning it. I wrote "at least n+1" to not rule out that case. $\endgroup$ – Manfred Weis Feb 3 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.