[MrXaK]

Здравствуйте,
есть много точек в многомерном пространстве (допустим M точек в N-мерном)
есть ещё одна точка, надо найти одну ближайшую к ней
можно ли решить эту задачу как либо кроме полного перебора всех декартовых расстояний до каждой точки?
если поможет, то все точки из M имеют как минимум одну нулевую координату в пространстве,
точка, для которой надо найти ближайшую, точно нулевых координат не имеет
допускается найти ближайшую с некоторой (достаточно малой, но конечной) погрешностью, то есть, грубо говоря ближайших может быть несколько и нужна одна из них

@темы: Алгоритм

Comments

[Trotil]

А эта процедура однократная или многократная?
Если первое, то без перебора не обойтись (можно задать параметр "а" и по его достижении a < |x-x0| останавливать перебор).
Если второе, тогда имеет смысл подготовить дополнительные данные, например сгруппировать точки и тогда сравнений будет заведомо меньше. Под группировкой я имею ввиду следующее: можно выделить подобласти одинакового радиуса (N-мерные шары), в каждом шаре с центром M_i k_i точек. Ясно, что проверка |M_i-x0| < R0 будет означать, что точка x0 лежит в шаре M_i и достаточно будет перебрать точки этой области. В свою очередь пространство в шаре можно разбить еще на подшары и т.д. Естественно, затрачивается время на подготовку, зато поиск будет существенно быстрее.

[MrXaK]

она что-то среднее, в рамках одного запуска программы искомая точка разная, а опорные точки M одинаковые в разных запусках
про шары тоже думал, правда в многомерном пространстве не представляю))) в трехмерном случае я думал стоит взять, например, точку, ближайшую по какой-то координате, рисовать шар радиусом в неё и смотреть линию пересечения прямой от точки до опорной точки, если пересекает шар после точки, значит внутри и её за радиус.. но то в трёхмерном - трёхмерное пространство можно нарисовать (я использую python+vtk а в vtk есть средства, которые позволяют проверить с какой стороны отрезок пересекатся с поверхностью), а вот многомерное уже так не нарисуешь и не проверишь графически.. а с математической точки зрения всё равно ведь прийдётся каждую точку считать ( |M_i-x0| это же по идее и есть декартовое расстояние, если я правильно понимаю), то есть будет как первый случай.. или хз, может чего-то не понимаю

[Trotil]

она что-то среднее, в рамках одного запуска программы искомая точка разная, а опорные точки M одинаковые в разных запусках

Тогда их можно подсчитать до итоговой компиляции (типа, промежуточная задача) и вставить исходными данными вместе с опорными точками.

про шары тоже думал, правда в многомерном пространстве не представляю)))

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

а с математической точки зрения всё равно ведь прийдётся каждую точку считать

нет, не каждую. Каждый центр до первого попадания. А центров всего sqrt(M) или даже log2(M) в идеале.