how do you calculate co-ordinates of point based on constraints relative to other points?

Question

Let me know if this is mathoverflow material, and I'll wend my way over there. I'm hoping someone will recognise this and point me in the right direction...

I'm trying to map out related nodes. I've figured out how to calculate the minimum distances between all the points, and now I need to know how to turn those into actual co-ordinates in 2D space.

So, given a point P_n (where n > 1), a set of points [P₁..P_n-1], and a set of distances [d₁..d_n-1] where each d represents the minimum distance between P_n and d's respective point, how do I calculate the best valid co-ordinate set [x,y] for P_n?

When I say 'best' valid co-ordinate set, I mean the set that brings P_n closest to all the other points without violating any of the constraints.

My first thought was to stick P₁ at [0,0], P₂ at [0,d] (d₁ for P₂) and then for P₃ I would put it at [0,y] where y is the minimum distance that P₃ has to be at to satisfy its d₁ and d₂ and then move it in a circle around P₂ at a radius of d₂ for as long as it still satisfies d₁.

That would have to be repeated for all points, which sounds like it would take ages.

Does this problem ring any bells with anyone? I'm not sure what formula or algorithms I'm looking for.

Update I hadn't thought about what 'closest' means. I knew what I meant when I wrote it, but I hadn't thought about calculating it!

Minimum sum of squares sounds like it will do the job.

Answer 1

It sounds a lot as if you're trying to do some form of multidimensional scaling.

Answer 2

My guess is that in general this would be hard. What you are doing is starting with the whole plane, then removing discs (of radius d) around each of your existing Ps, and then asking - where on this mutilated plane is the point 'closest' to all the existing Ps?

Even once you've decided what you mean by 'closest' (minimize sum of squared distance is traditional, but that might not be what you want), you are still faced with the problem that the mutilated plane can in the general case be of an arbitrarily complicated shape. I would suggest you do head over to mathoverflow.

Answer 3

The solution, without the constraints, is to set

P_n = Σ_i=1^n-1 P_i / (n-1)

(With constraints is more difficult; I have an idea of how to do it, see my advice below)

Proof

We are looking to minimize

Σ_i=1^n-1 ||P_n - P_i||²
= Σ_i=1^n-1 (P_n - P_i)·(P_n - P_i)
= Σ_i=1^n-1 P_n·P_n - 2P_n·P_i + P_i·P_i
= Σ_i=1^n-1 P_n·P_n - Σ_i=1^n-1 2P_n·P_i + Σ_i=1^n-1 P_i·P_i
= (n-1)P_n·P_n - 2P_n·Σ_i=1^n-1 P_i + Σ_i=1^n-1 P_i·P_i

Since we are in 2d, this is a quadratic equation of 2-variables; we can take the partial-derivatives to find the critical-point (and thus the minimum):

f = (n-1)P_nx² + (n-1)P_ny² - 2P_nxΣ_i=1^n-1 P_ix - 2P_nyΣ_i=1^n-1 P_iy + Σ_i=1^n-1 P_i·P_i (constant, so doesn't matter for derivative)
D_xf = 2(n-1)P_nx - 2Σ_i=1^n-1 P_ix
D_yf = 2(n-1)P_ny - 2Σ_i=1^n-1 P_iy

Setting those last two derivatives to 0, we get the result.

This is known as a barycentric combination (or barycenter, or center of mass or whathave you). While this doesn't answer your question, the last equation should help:

k = (n-1)P_n·P_n - 2P_n·Σ_i=1^n-1 P_i + Σ_i=1^n-1 P_i·P_i

Where k is some constant. If we were to graph this on a plane, then for some k we'd get a single point: P_n, our barycenter. As we increased k, we'd get the graph of a circle centered at P_n - all the points on this circle have the same sum-of-squares value. As we increase k, this sum-of-squares value gets larger and larger.

If we were going to solve this mathematically and rigerously, we'd want to find the smallest k which creates a circle which has a point that satifies all the constraints. I don't know how we'd do that.

To estimate the answer in a program, I'd keep creating larger and larger circles centered around our barycenter until we find one that works. To determine if a circle works: find all collision points of our barycentric-circle with all the other circles created by the constraints, and everyplace our circle collides with another, create a cut point. With all our cut-points, we've divided our circle into arcs (no more than 2n-1 arcs, unless our center is exactly one of the points) - all points on each arc will share the same status of "satisfying the constraints or not", so choose any point on the arc to test it. Do this for all arcs on the circle, and if none of them satisfy it, make the circle a little bit bigger.

We could make this a bit better by noticing that increasing the circle-size doesn't help any if we're still colliding the same amount of times with all the same circles.