расстояние межу точками

[malefik]

Доброго времени суток!
Вопросик думаю не тяжелый но все-же.
Есть массив mass1 из точек с координатами x1,y1...x10,y10...xn,yn
Есть точка с координатами xa,ya.
Вопрос ....по каким мормулам найти в mass1 ближайшую точку к xa,ya.
Спасибо. поиск юзал но не нашел ничего на форуме.
Если есть возможность ткните носом.

[meduza]

Есть в любом учебнике по аналитической геометрии. И в школьной геометрии тоже.

[Профессор Снэйп]

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

-- Сб дек 12, 2009 19:51:54 --

Какая Вас формула, в самом деле, интересует? Расстояние между точками $(x_a,y_a)$ и $(x_i,y_i)$? Оно равно $\sqrt{(x_a-x_i)^2 + (y_a-y_i)^2}$.

[Sasha2]

Следует ли это понимать, что данная задача просто эквивалентна задаче, найти наименьшее число из n данных чисел?

[Профессор Снэйп]

Мне просто больше ничего в голову не приходит. Потому и предположил, что это задача по программированию; дескать, дан массив из $n$ точек и ещё одна точка, надо найти точку массива, ближайшую к данной.

(Оффтоп)

Ник malefik намекает на силы зла. Может, не стоит ему помогать, дабы не приближать торжество дьявола?

[PAV]

Профессор Снэйп, предупреждение за комментирование ников!

[malefik]

думаю лучше в программирование

Профессор Снэйп в сообщении #270664 писал(а):

Мне просто больше ничего в голову не приходит. Потому и предположил, что это задача по программированию; дескать, дан массив из $n$ точек и ещё одна точка, надо найти точку массива, ближайшую к данной.

(Оффтоп)

Ник malefik намекает на силы зла. Может, не стоит ему помогать, дабы не приближать торжество дьявола?

прав

[Sasha2]

Наверное единственное, что Вам тут поможет (если это можно так назвать), так это только использование равносильности двух неравенств

$(x_1-a)^2+(y_1-b)^2\geq{(x_2-a)^2+(y_2-b)^2}$
и
$(x_1-x_2)(x_1+x_2-2a)+(y_1-y_2)(y_1+y_2-2b)\geq{0}$

Умножений меньше. Хотя, стоит ли оно того, ведь не миллион же точек у Вас.

[Профессор Снэйп]

Точек, по условию задачи, $n$ штук Как в анекдоте про военных: "Пусть у противника $n$ танков... нет, $n$ слишком мало, пусть будет $m$ танков!"

Если уж оптимизировать алгоритм, предполагая, что количество точек будет очень велико... Можно, в первом приближении, искать минимальное расстояние в метрике $|x_a-x_i| + |y_a-y_i|$, там умножать ничего не надо, а с обычной евклидовой метрикой она очень хорошо связана. Но это уже действительно лучше обсуждать в программировании.

[ewert]

Профессор Снэйп в сообщении #270727 писал(а):

предполагая, что количество точек будет очень велико...

(Оффтоп)

вот тогда уж точно надо $N$, а не $n$

Профессор Снэйп в сообщении #270727 писал(а):

искать минимальное расстояние в метрике $|x_a-x_i| + |y_a-y_i|$, там умножать ничего не надо, а с обычной евклидовой метрикой она очень хорошо связана.

Это как это-как это связана?...

[Xaositect]

ewert в сообщении #270736 писал(а):

Это как это-как это связана?...

Ну как же. Любые две нормы в $\mathbb{R}^n$ эквивалентны, так что вот. Только в данной задаче это сильно не помогает.

[ewert]

Xaositect в сообщении #270739 писал(а):

Ну как же. Любые две нормы в $\mathbb{R}^n$ эквивалентны, так что вот. Только в данной задаче это сильно не помогает.

Зато сильно вредит: эквивалентность норм никак с этой задачей не связана.

[Профессор Снэйп]

ewert в сообщении #270740 писал(а):

Зато сильно вредит: эквивалентность норм никак с этой задачей не связана.

Может навредить, а может и помочь. В типичном случае скорее помогает, чем вредит.

Пусть $\| \cdot \|_1$ --- норма с модулями, $\| \cdot \|_2$ --- евклидова норма. Справедливо $\| x \|_1 \leqslant \| x \|_2 \leqslant 2 \| x \|_1$. Теперь если евклидово расстояние от $(x_a,y_a)$ до различных точек массива различается больше, чем в $2$ раза, то можно смело использовать норму $\| \cdot \|_1$ и будет найдена нужная точка. А если разброс расстояний просто велик, то можно сначала из огромного массива точек выделить малую часть таких точек, что расстояние от выбранной до каждой из них в норме $\| \cdot \|_1$ не более чем в $2$ раза больше чем расстояние от выбранной до минимальной в той же норме, а потом этой части уже смотреть минимум по евклидовой норме.

Просто норму $\| \cdot \|_1$ считать проще, чем норму $\| \cdot \|_2$, там не надо ничего перемножать. Если для гигантского числа случаев нужно будет считать $\| \cdot \|_1$, а затем лишь для малого числа этих случаев $\| \cdot \|_2$, то получится быстрее, чем для всех без исключения случаев считать $\| \cdot \|_2$.

[PAV]

Вообще-то далеко не факт, что быстрее. Вычисление модуля требует условного перехода (сменить знак, если отрицательно); на современных процессорах это будет работать медленнее, чем умножения без каких-либо условий.

[Xaositect]

2Профессор Снэйп
Да ну, умножение не настолько медленнее сложения. Данные читать все равно дольше будет.