восстановить координаты точек структуры по расстояниям

[allchemist]

доброго времени суток.
столкнулся с такой проблемой.
есть набор точек, известны расстояния между каждой парой точек
нужно подобрать структуру, координаты точек которой соответствуют набору расстояний
кто-нибудь знает, как делать, или хотя бы куда копать?

[AD]

Что значит "структуру"? Просто как-то расставить в пространстве $N$ точек $A_1,\ldots,A_n$ так, чтобы расстояния между $A_i$ и $A_j$ были равны заданным $d_{ij}$?

Ну вроде бы всё тривиально.

Первую точку можно поставить куда угодно.

Вторую - в любую точку на сфере радиуса $d_{12}$ вокруг первой.

Третью - на окружность - пересечение сфер $S_{d_{13}}(A_1)\cap S_{d_{23}}(A_2)$ (понятны обозначения?)

Четвертую - в пересечение трех сфер, т.е., фактически, будут две точки на выбор.

Дальше вообще все однозначно определяется. Берем любые четыре уже поставленные точки (скажем, всё время это будут первые четыре), и по ним и расстояниям до них однозначно определяем координаты новой.

Если входные данные заведомо корректны, то задачу мы решим, причем, фактически, за оптимальное время - $O(N)$ по времени и $O(1)$ по памяти.

[allchemist]

спасибо, попробую

AD писал(а):

Что значит "структуру"? Просто как-то расставить в пространстве $N$ точек $A_1,\ldots,A_n$ так, чтобы расстояния между $A_i$ и $A_j$ были равны заданным $d_{ij}$?

да
в общем виде задача в оптимизации структуры молекулярного кластера
ради простоты вычисления представил структуру в виде набора межатомных расстояний
произвел рассчеты, нашел минимальную энергию, а "посмотреть" на полученный результат не могу

[Yuri Gendelman]

allchemist писал(а):

есть набор точек, известны расстояния между каждой парой точек
нужно подобрать структуру, координаты точек которой соответствуют набору расстояний
кто-нибудь знает, как делать, или хотя бы куда копать?

Пусть у Вас есть $N$ точек, определяемых $3 N$ координатами. Известны $\frac {N (N-1)} {2}$ расстояний.
Вы должны решить систему $\frac {N (N-1)} {2}$ уравнений с $3 N$ неизвестными вида:
$(X_i - X_j)^2 + (Y_i - Y_j)^2 + (Z_i - Z_j)^2 = R_{i,j}^2$ , где $1 \le i < j \le N$
Но при $N > 7$ эта система переопределена.

Попробуйте решать оптимизационную задачу - ищите минимум суммы квадратов ошибок в расстояниях:
$(\sum_{i<j}{(\sqrt{(X_i - X_j)^2 + (Y_i - Y_j)^2 + (Z_i - Z_j)^2} - R_{i,j})^2}) \rightarrow min$

[rtfai]

http://www.ipsi.smr.ru/research/publica ... 311210.pdf

Но проблема становится нетривиальной, если число заданных расстояний сравнимо с числом точек.