CODEWITHSUNDEEP
multidimensional-arraygeometrylinear-algebracomputational-geometry
ErroneousFatality
ErroneousFatality

Reputation: 476

Create sphere in d dimensions using (d+1) points (or less)

Say I have N points in D-dimensional space; where N can be a number from 4 up to D+1.

I want to create the smallest possible sphere defined by these N points, or in other words, a minimal sphere which contains all N points (it passes exactly through all of them).

The variables of the solution are it's center and radius.

I'm bad with matrices, and I guess this problem requires them?

Upvotes: 1

Views: 135

Answers (1)

Darren Engwirda
Darren Engwirda

Reputation: 7015

I believe that you're looking for a (minimal) circumsphere for your points x. As you've suggested, such an object can be calculated via a bit of linear algebra.

Given a set of m points x in n dimensions (m <= n+1), such that:

x = [x_11, x_12, ..., x_1n]
    [x_21, x_22, ..., x_2n]
    .
    .
    .
    [x_m1, x_m2, ..., x_mn]

It's possible to write down the equations for a common sphere of radius R, centred at X = [X_1,X_2,...,X_n] that passes through each of the points in x:

(x_11 - X_1)^2 + (x_12 - X_2)^2 + ... + (x_1n - X_n)^2 = R^2      (1)
(x_21 - X_1)^2 + (x_22 - X_2)^2 + ... + (x_2n - X_n)^2 = R^2      (2)
.
.
.
(x_m1 - X_1)^2 + (x_m2 - X_2)^2 + ... + (x_mn - X_n)^2 = R^2      (m)

Expanding the quadratic terms in each equation, subtracting (1) from equations (2)--(m), and doing a little manipulation, leads to a set of linear equations for the centre X:

M * X = B

where:

M = [x_11-x_21, x_12-x_22, ..., x_1n-x_2n]
    .
    .
    .
    [x_11-x_m1, x_12-x_m2, ..., x_1n-x_mn]

B = [x_11^2-x_21^2 + x_12^2-x_22^2 + ... + x_1n^2-x_2n^2] * (1/2)
    .
    .
    .
    [x_11^2-x_m1^2 + x_12^2-x_m2^2 + ... + x_1n^2-x_mn^2] * (1/2)

Note that M is an (m-1) x n matrix, while B is an (m-1) x 1 vector.

Clearly, when m = n+1, the matrix is square, and there is a unique solution for the centre X, fully describing the circumsphere associated with the points x. (The radius can be obtained as the distance from X to any x_i).

When m < n+1 the solution is non-unique, and there are an infinite family of circumspheres. In such cases, additional constraints need to be added to the matrix M to give a solution.

In your case, I believe that you may be wishing to constrain X to lie on the common hyperplane described by the points x, but I'll have a bit more of a think about this...

Upvotes: 1

Related Questions