Как вы рассчитываете координаты точки на основе ограничений относительно других точек?

Question

Дайте мне знать, если это материальный поток, и я отправлюсь туда. Я надеюсь, что кто-то узнает это и укажет мне правильное направление ...

Я пытаюсь наметить связанные узлы. Я выяснил, как рассчитать минимальные расстояния между всеми точками, и теперь мне нужно знать, как превратить их в реальные координаты в 2D-пространстве.

Итак, учитывая точку P _n (где n> 1), набор точек [P ₁ .. P _n-1 ], и набор расстояний [d ₁ .. d _n-1 ], где каждый d представляет минимальное расстояние между P _n и соответствующей точкой d, как Я рассчитываю лучший действительный набор координат [x, y] для P _n ?

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

Моей первой мыслью было поставить P ₁ в [0,0], P ₂ в [0, d] (d ₁ для P ₂ ), а затем для P ₃ я бы поставил его на [0, y], где y - это минимальное расстояние, на котором P ₃ должно быть, чтобы удовлетворить его d ₁ и d ₂ , а затем переместите его по кругу вокруг P ₂ в радиусе d ₂ до тех пор, пока все еще удовлетворяет d ₁ .

Это должно было бы быть повторено для всех точек, похоже, это заняло бы целую вечность.

Эта проблема звонит кому-нибудь? Я не уверен, какую формулу или алгоритмы я ищу.

Обновление Я не думал о том, что значит «самый близкий». Я знал, что имел в виду, когда писал, но не думал об этом!

Минимальная сумма квадратов звучит так, как будто это сделает работу.

Answer 1

Решение без ограничений - установить

P _n = Σ _{i = 1} ^n-1 P _i / (n-1)

(С ограничениями труднее; у меня есть идея, как это сделать, см. Мой совет ниже)

Доказательство

Мы стремимся свести к минимуму

Σ _{i = 1} ^n-1 || P _n - P _i || ²
= Σ _{i = 1} ^n-1 (P _n - P _i ) · (P _n - P _я )
= Σ _{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 _я
= (n-1) P _n · P _n - 2P _n · Σ _{i = 1} ^n-1 P _i + Σ _{i = 1} ^n-1 P _i · P _i

Поскольку мы находимся в 2d, это квадратное уравнение 2-переменных; мы можем взять частные производные, чтобы найти критическую точку (и, следовательно, минимум):

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 (постоянный, поэтому не имеет значения для производной)
D _x f = 2 (n-1) P _nx - 2Σ _{i = 1} ^n-1 P _ix
D _y f = 2 (n-1) P _ny - 2Σ _{i = 1} ^n-1 P _iy

Если установить последние две производные равными 0, мы получим результат.

Это известно как барицентрическая комбинация (или барицентр , или центр масс или что у вас есть). Хотя это не отвечает на ваш вопрос, последнее уравнение должно помочь:

k = (n-1) P _n · P _n - 2P _n · Σ _{i = 1} ^n-1 P _i + Σ _{i = 1} ^n-1 P _i · P _i

Где k - некоторая постоянная. Если бы мы нарисовали это на плоскости, то для некоторого k мы получили бы одну точку: P _n , наш барицентр. При увеличении k мы получим график окружности с центром в P _n - все точки на этом круге имеют одинаковое значение суммы квадратов. При увеличении k это значение суммы квадратов становится все больше и больше.

Если бы мы собирались решить это математически и тщательно, мы бы хотели найти наименьшее k, которое создает круг, имеющий точку, которая удовлетворяет всем ограничениям. Я не знаю, как мы это сделаем.

Чтобы оценить ответ в программе, я продолжал бы создавать все большие и большие круги вокруг нашего барицентра, пока мы не найдем тот, который работает. Чтобы определить, работает ли круг: найдите все точки столкновения нашего барицентрического круга со всеми другими кругами, созданными ограничениями, и везде, где наш круг сталкивается с другим, создайте точку разреза. Со всеми нашими точками среза мы разделили наш круг на дуги (не более 2n-1 дуг, если только наш центр не является точно одной из точек) - все точки на каждой дуге будут иметь одинаковый статус " удовлетворяет ограничениям или нет ", поэтому выберите любую точку на дуге, чтобы проверить ее. Сделайте это для всех дуг в круге, и если ни одна из них не удовлетворяет его, сделайте круг немного больше.

Мы могли бы сделать это немного лучше, заметив, что увеличение размера круга ни к чему не приведет, если мы все еще сталкиваемся одинаковое количество раз со всеми одинаковыми кругами.

Answer 2

Звучит так, как будто вы пытаетесь выполнить некую форму многомерного масштабирования .

Answer 3

Я предполагаю, что в целом это будет сложно. Вы начинаете со всей плоскости, затем удаляете диски (радиус d) вокруг каждой из ваших существующих P с, а затем спрашиваете - где на этой изуродованной плоскости находится точка, "ближайшая" ко всем существующим P s

Даже если вы решили, что вы подразумеваете под «самым близким» (минимизировать сумму квадратов расстояния традиционно, но это может быть не то, что вам нужно), вы все равно столкнетесь с проблемой, которую может изуродовать самолет в общем случае имеет произвольно сложную форму. Я бы посоветовал вам отправиться в Mathoverflow.