# How does one compute the minimal bounding sphere of a k-simplex?

Suppose I have a list of $k+1$ points in $\mathbb{R}^n$, and I let $\sigma^k$ be their convex hull. I want to know two things:

1. How can I determine, for any $\varepsilon$, whether open balls of radius $\varepsilon$ centered at each point intersect?
2. More generally, how can I compute the center of the minimal bounding sphere $S^{k+1}$ of $\sigma^k$, which would then tell me the infimal value of $\varepsilon$ in #1?

My main concern is whether these can be done efficiently (a linear time algorithm in $k$ to compute #2 would be wonderful). In general it is not the case that this polytope is cyclic (or else I could take any two faces and intersect perpendicular lines from their centers to compute the circumcenter).

Just in case this is relevant, I want to know this so I can build a Cech complex from the data for any parameter $\varepsilon$, and determine which values of $\varepsilon$ at which the complex changes.

-

## 2 Answers

1. You need to compute the distances ($\frac{n(n-1)}2$ calculations, using the Pythagorean thm), and insure that $X_iX_j > 2\varepsilon$ for all distinct pairs $X_i,X_j$ of vertices.

2. Calculate the equations of the midperpendicular plane of $X_0,X_1$ and that of $X_1,X_2$ and so on.. ($n$ calculations), and find their intersection point.

-

I think you're describing a Rips complex, and that is not the same as a Cech complex. Specifically, the vertices of an equilateral triangle would have balls with pairwise intersections, but no three-way intersection. – Bean Sep 30 '12 at 17:16

miniball ${}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}$

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 18, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9302401542663574, "perplexity_flag": "head"}