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.

I'm working with the Bowyer-Watson algorithm to determine the Delaunay tessellation of stochastic points in k-dimensional space. This algorithm assumes that the center of a simplex can be used as the center of the unique hypersphere (circum-hypersphere?) defined by the simplex's points, and I have found examples where this does not hold true (e.g., obtuse triangles in 2D space).

I need to be able to determine as exactly as possible whether a new point added to the space falls within an existing circum-hypersphere, because this tessellation is going to be used for spatial analysis. The problem is that I have not found an algorithm for doing this that I understand. The closest I've come is at http://www.oocities.org/kiranisingh/center.html , but the general equation at the bottom uses a convention that I've never seen before... it looks like the formulas require dividing two matrices and getting a scalar result?

How do I calculate the unique k-dimensional hypersphere's center from k+1 points? I would appreciate as tutorial an approach as can be provided.

share|improve this question
    
After some more research, I realized that the equations on that page are using Cramer's rule... those are the determinants of the matrices, not the matrices themselves. –  gamecoder Jan 26 '12 at 17:32

1 Answer 1

up vote 3 down vote accepted

The centre of your hypersphere should be equidistant from all of your given points. Say the points are ${\bf p}_1, \ldots, {\bf p}_{k+1}$ in ${\mathbb R}^k$. For each $i$ from $1$ to $k$, the points equidistant from ${\bf p}_i$ and ${\bf p}_{i+1}$ form a hyperplane with the equation $ ({\bf p}_i - {\bf p}_{i+1}) \cdot {\bf x} = ({\bf p}_i - {\bf p}_{i+1}) \cdot ({\bf p}_i + {\bf p}_{i+1})/2$. Solve this system of $k$ equations in $k$ variables (the coordinates of $\bf x$), and when you get a unique solution (which happens with probability $1$ if the points are chosen randomly with a continuous density), it gives you your centre.

share|improve this answer
    
Your answer helped me to figure out the equations on the original page I found. Are your equations the same as those on that page, or am I mistaken? –  gamecoder Jan 26 '12 at 17:36

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.