Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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

share|improve this answer
  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.

share|improve this answer
    
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. –  JeremyKun Sep 30 '12 at 17:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.