CODEWITHSUNDEEP
geometrycomputational-geometry
ErroneousFatality
ErroneousFatality

Reputation: 476

Calculate equidistant point with minimal distance from 3 points in N-dimensional space

I'm trying to code the Ritter's bounding sphere algorithm in arbitrary dimensions, and I'm stuck on the part of creating a sphere which would have 3 given points on it's edge, or in other words, a sphere which would be defined by 3 points in N-dimensional space.

That sphere's center would be the minimal-distance equidistant point from the (defining) 3 points.

I know how to solve it in 2-D (circumcenter of a triangle defined by 3 points), and I've seen some vector calculations for 3D, but I don't know what the best method would be for N-D, and if it's even possible.

(I'd also appreciate any other advice about the smallest bounding sphere calculations in ND, in case I'm going in the wrong direction.)

Upvotes: 3

Views: 3055

Answers (2)

Jack Ritter
Jack Ritter

Reputation: 411

My Bounding Sphere algorithm only calculates a near-optimal sphere, in 3 dimensions.

Fischer has an exact, minimal bounding hyper-sphere (N dimensions.) See his paper: http://people.inf.ethz.ch/gaertner/texts/own_work/seb.pdf.

His (C++/Java)code: https://github.com/hbf/miniball.

Jack Ritter [email protected]

Upvotes: 1

Spektre
Spektre

Reputation: 51835

so if I get it right:

Wanted point p is intersection between 3 hyper-spheres of the same radius r where the centers of hyper-spheres are your points p0,p1,p2 and radius r is minimum of all possible solutions. In n-D is arbitrary point defined as (x1,x2,x3,...xn)

so solve following equations:

|p-p0|=r
|p-p1|=r
|p-p2|=r

where p,r are unknowns and p0,p1,p2 are knowns. This lead to 3*n equations and n+1 unknowns. So get all the nonzero r solutions and select the minimal. To compute correctly chose some non trivial equation (0=r) from each sphere to form system of n+1 =equations and n+1 unknowns and solve it.

[notes]

To ease up the processing you can have your equations in this form:

(p.xi-p0.xi)^2=r^2

and use sqrt(r^2) only after solution is found (ignoring negative radius).

there is also another simpler approach possible:

You can compute the plane in which the points p0,p1,p2 lies so just find u,v coordinates of these points inside this plane. Then solve your problem in 2D on (u,v) coordinates and after that convert found solution form (u,v) back to your n-D space.

plane u,v coordinates

n=(p1-p0)x(p2-p0); // x is cross product
u=(p1-p0); u/=|u|;
v=u x n; v/=|v|; // x is cross product

if memory of mine serves me well then conversion n-D -> u,v is done like this:

P0=(0,0);
P1=(|p1-p0|,0);
P2=(dot(p2-p0,u),dot(p2-p0,v));

where P0,P1,P2 are 2D points in (u,v) coordinate system of the plane corresponding to points p0,p1,p2 in n-D space.

conversion back is done like this:

p=(P.u*u)+(P.v*v);

Upvotes: 3

Related Questions