Минимизировать евклидово расстояние от наборов точек в 3-й

Question

Давайте посмотрим на четыре (m) точки в трехмерном пространстве - я хочу обобщить на n-d, но для решения должно хватить 3 (часть 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.

Какие алгоритмы можно использовать? Идея или псевдокод достаточно.

Часть 2: решить для m точек в n-измерениях:

Я думал, что было бы несложно обобщить m точек в n измерениях, но оказалось, что это не так просто. Я создал еще одну проблему для общей проблемы здесь: минимизировать евклидово расстояние от множеств точек в n-измерениях

Answer 1

Я думаю, что ваш вопрос в 3D можно свести к простой задаче аффинной 2D геометрии, проецируя точку P на плоскость, определяемую тремя точками A, B, C или двумя векторами AB и AC ( или другие комбинации AB, AC, and BC).

На первый взгляд кажется вероятным, что задача 3 + 1 баллов обобщается на N измерений (3 точки всегда определяют треугольник и плоскость).
Однако не сразу ясно, будет ли этот подход работать для большего количества точек, которые не будут копланарными.

1- приведение к 2D путем проецирования P в точку P' на плоскость, заданную векторами AB и AC.

2 - понять, что позиция P' определяется только одним коэффициентом t in the Reals с.т. P' является аффинной комбинацией AB и AC:
P' = t * AB + (1-t) * AC

3 - оттуда, P' может быть в 3 различных местах:

• (а) внутри треугольника ABC: в этом случае Q = P'

• (b) в областях, ограниченных ортогональной проекцией наружу один из сегментов; в этом случае Q является ортогональной проекцией P' на ближайшем сегменте.

• (c) не в (a) или (b); в этом последнем тривиальном случае Q является ближайшим из A, B, or C

---