Визуализация графа. Как расположить точки на плоскости?

[Aleco]

Помогите пожалуйста подобрать правильный алгоритм для слудующей задачи.

Имеем набор из N точек. Для каждой пары точек А и В известно некоторое "оптимальное" или "желаемое" расстояние между ними. По смыслу - точки с расстояниями - это некий социальный граф. Необходимо визуализировать граф и расположить точки на плоскости таким образом, чтобы итоговые геометрические расстояния между точкам на плоскости были максимально приближенны к желаемым.

Очевидно, что полного совпадения с желаемыми растояниями может не получится. Даже три точки могут иметь противоречивые взаимные расстояния. Так что ищем некий оптимум. Критерий оптимальности реальных и желаемых расстояний - сумма квадратов их разниц для каждой точки должна быть минимальной. Впрочем, подойдет и другой, похожий критерий. Например имеет смысл ориентироваться на отношение реального и желаемого расстояния, а не их разницу.

Так же возможно что математически наилучший ответ найти трудно, а вот некоторое приближенное решение - гораздо проще.Например применив итеративный подход. Тогда подойдет приближенное.

// Уже сформулировав условие этой задачи я понял что не знаю как решить даже более простую. Предположим что у нас уже размещено на плоскости N точек. И надо добавить еще одну, чтобы максимально точно подобрать желаемые расстояния от новой точки до каждой из N существующиих. Как это сделать?

[Mysterious Light]

У Вас есть $N$ точек и $N(N-1)/2$ положительных чисел $\left[0,+\infty\right]$ (бесконечность как или маркер несвязности, или неоднозначности в трактовке, или ещё чего-нибудь), выражающих [желаемое] расстояние между любыми двумя точками, и Вам необходимо их красиво изобразить, чтоб геометрическое расстояние было максимально приближено к желаемому. Я правильно понял?

Из того, что я слышал, мне запомнился такой алгоритм. Его суть заключается в следующем: каждую вершину графа мыслим как материальную точку, а каждое ребро — как пружину, а затем моделируем поведение физической системы до того момента, как она придёт в своё положение равновесия, которое мы и отображаем на экране. Здесь можно подобрать удобные аналогии. Так, пружина может подчинятся разным законам (пропорциональному, линейному или логорифмическому по смещению), что даёт желаемый Вами выбор в том, что именно минимизируется. С другой стороны, можно ввести достаточно ощутимую диссипацию (а алгоритм сам по себе имеет проблему локального минимума, то есть часто выдаёт не абсолютный минимум, а локальный) и тогда при добавлении новой точки к уже отрисованному графу положение уже отрисованных точек особо не изменится (что, как мне кажется, должно часто случаться при полной минимизации, когда мы попадаем не в ближайший существенно-глубокий локальный минимум). Детальнее смотрите википедию. Такой метод подходит?

[Aleco]

Супер! Это в точности то что мне было нужно!!!

Огромное спасибо!