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