1
$\begingroup$

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 2

3

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

1
  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.

  • 0
    I think you're describing a Rips complex, and that is not the same as a Cech complex. Speci$f$ically, the vertices o$f$ an equilateral triangle would have balls with pairwise intersections, but no three-way intersection.2012-09-30