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:
- How can I determine, for any $\varepsilon$, whether open balls of radius $\varepsilon$ centered at each point intersect?
- 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.