4
$\begingroup$

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.

  • 0
    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.2012-01-26

1 Answers 1

4

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.

  • 0
    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?2012-01-26