Minimize Euclidean distance from sets of points in 3-d

Question

Let's look at four (m) points in 3-d space- I want to generalize to n-d, but 3 should suffice for a solution ( Part 1).

a= (x1, y1, z1)

b= (x2, y2, z2)

c= (x3, y3, z3)
.
.

p= (x , y , z)

Find point q = c1* a + c2* b + c3* c + ..

where c1 + c2 + c3 +.. = 1
and  c1, c2, c3, .. >= 0
s.t.
euclidean distance pq is minimized.

What algorithms can be used ? Idea or pseudocode is enough.

Part 2: solve for m points in n-dimensions :

I thought it would be trivial to generalize to m points in n dimensions, but turns out it is not straightforward. I created another problem for the general problem here: minimize euclidean distance from sets of points in n-dimensions

1) `x1+x2+x3` is a scalar, not a vector. Perhaps you meant `(x1,x2,x3)`. 2)This is more of a math question than a programming question. [mathematics.se] would be a better fit 3) Let `f(c1,c2,c3) = (d(p,q))^2`. Find the gradient of `f` and set it equal to zero. — John Coleman, Sep 01 '18 at 15:44
Is the equation `c1 + c2 + c3 = 1` the only condition on `c1,c2,c3`? If so, if the points `a,b,c` are not collinear then point `q` can be any point in the plane defined by `a,b,c`. If those points are collinear but not identical then point `q` can be any point on the line defined by the points. If those points are identical then `q` is only that point. Are you sure there are not the additional conditions that `c1>=0`, `c2>=0`, `c3>=0`? Those would restrict `q` to the triangular region made by points `a,b,c`. All this should point you to a solution. — Rory Daulton, Sep 01 '18 at 16:56
Assuming that you are assuming that the `c_i` are positive, you are asking for the the point `q` on the *convex hull* of the given points. See [this question](https://math.stackexchange.com/q/2146961/294695) on [mathematics.se]. Coding it by hand would be burdensome (especially in higher dimensions as you seem to want to do) but any good quadratic programming library could handle this easily. — John Coleman, Sep 01 '18 at 17:23

Reblochon Masque · Accepted Answer · 2018-09-02T06:58:19.163

1

I think your question in 3D can be reduced to a simple affine 2D geometry problem by projecting the point P on the plane defined by the three points A, B, C, or the two vectors AB and AC (or another combinations of AB, AC, and BC).

At first sight, it seems likely that the 3+1 points problem generalizes to N dimensions (3 points always defining a triangle and a plane).
However, it is not immediately clear if this approach would work for more points that would not be coplanar.

1- reduction to 2D by projecting P to a point P'on the plane defined by vectors AB, and AC.

2- understand that the position of P' is determined by only one coefficient t in the Reals s.t. P' is an affine combination of AB and AC :
P' = t * AB + (1-t) * AC

3- from there, P' can be in 3 distinct locations:

(a) inside the triangle ABC: in that case, Q = P'
(b) in the areas delimited by an orthogonal outwards projection of one of the segments; in that case Q is the orthogonal projection of P' on the closest segment.
(c) not in (a) or (b); in that last trivial case, Q is the closest of A, B, or C

edited Sep 02 '18 at 06:58

answered Sep 02 '18 at 03:24

Reblochon Masque

35,405
10
55
80

Not sure I follow. Let's say: a = (0, 0, 0 ) b= (2, 0, 0) c= (0, 2, 0) p = (1, 1, 1) Here, I think p' = (1, 1, 0 ) = q and dist(pq) = 1. Somehow you would put q on the boundary. Also, I should update, I would like a solution with m points (e.g. a, b, c, d....) and p – Dumbo Sep 02 '18 at 04:54
Yes, you are correct, in your example `P' =(1, 1, 0)`, and `Q =(1, 1, 0)`, and `distance(PQ) = 1`. You should not change a question that explicitly states "four points", and "3 (dimensions) should suffice for a solution", to new requirements with m points and n dimensions. (but you could, of course, ask a new question that builds on this one) – Reblochon Masque Sep 02 '18 at 05:08
your point: "[P'] inside the triangle ABC; in that case, Q is the point on either segments AB, AC, or BC". - could you address/edit that? Also, if we add another point, D, still in 3-dimensions your solution would throw out the point that does not fall on the face (not plane) closest to P ( how would you define that? )- for P outside the shape, reducing it to your current solution. – Dumbo Sep 02 '18 at 05:33
`P'` inside `ABC`: you project `P'` on each of the segments `AB, AC, BC`, Q is the point on the closest segment. – Reblochon Masque Sep 02 '18 at 05:41
But as in my example above, P' is inside ABC however Q is not on one of the segments, but on the inside. – Dumbo Sep 02 '18 at 05:44
Adding a fourth point `D` not coplanar to `ABC` complicates matters; you now have 4 planes describing a tetrahedron. You can probably repeat this approach on each of the planes, find 4 points `Q`, then choose the closest to `P`, but there might be a better approach, IDK. – Reblochon Masque Sep 02 '18 at 05:45
In your example in the comments, `Q = (1, 1, 0)` is on the segment `BC`. – Reblochon Masque Sep 02 '18 at 05:46
say A= (0, 0, 0) B= (200, 0,0), C= (0, 200, 0). Q is still (1, 1, 0), but clearly not on line segment BC. no? – Dumbo Sep 02 '18 at 05:52
Actually, `P'` the projection of `P` on the plane `ABC` is at `(1, 1, 0)`, as I understood, `Q` is the closest projection of `P'` on the segments `AB, AC, BC`... if I misunderstood that part, then `Q = P'`, solved without further processing. – Reblochon Masque Sep 02 '18 at 05:58
for P' inside ABC, P' = Q always I think – Dumbo Sep 02 '18 at 05:59
Yes, `P'` is the closest point on the surface to `P`, your problem statement was maybe a bit ambiguous on that part. – Reblochon Masque Sep 02 '18 at 06:04
For P' inside (including boundary) ABC, P' = Q always I think, you should edit your answer so I can accept it. Thank you. Although, now I realize it's not trivial to generalize this to m points and n dimensions. I thought this would suffice. I was wrong. Do you mind if I edit the question to ask for the answer in two steps and I can accept your answer as solution to first part and leave it open? – Dumbo Sep 02 '18 at 06:11
ok, I am glad we eventually understood each other. I will edit my answer so `P'=Q` when `P'` lays inside `ABC`. You should probably ask a new question for the more general case though, linking to this one if you wish. – Reblochon Masque Sep 02 '18 at 06:14
I think it is helpful to have this for the second part. Your figure is good too you should keep it. I will reword to say part 1 and 2, you could just add one line on the top saying " solution to part 1" – Dumbo Sep 02 '18 at 06:24
I linked a new question (part 2), you do not need to add comment, but I think the figure was good. Also, this got -2 votes: an upvote would help. Thank you. – Dumbo Sep 02 '18 at 06:45

Minimize Euclidean distance from sets of points in 3-d

What algorithms can be used ? Idea or pseudocode is enough.

1 Answers1

Linked