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

хотелось бы не решать полным перебором точек.

возможно knnsearch который в opencv с этим справится?(только я не уверен там помоему приближённый алгоритм) или надо строить quad tree чтобы быстрее отсекать? 

+ потом еще надо точки которые непокрыты как то обвести баунд боксами, скажем делим все непокрытые точки опять же по расстоянию на группы, проверяем кол-во в группе если больше N, то обводим рамкой. 

http://en.wikipedia.org/wiki/Nearest_neighbor_search ?

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

Перестроение пространственного индекса (kd-дерева или чего-нибудь на основе диаграммы Вороного) вперемешку с поиском скорее всего только замедлит работу.

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

Еще такой вопрос про PCA.

Допустим у нас есть выборка из 1000 сэмплов(каждый вектор длиной N) и для 1001 надо найти скажем K ближайших соседей, можно было бы перебрать все по порядку используя например просто евклидову метрику для вектора длиной N и потом отсортировать и взять K ближайших сэмплов.
Но вроде бы такой подход никуда не годится, ибо при больших N это плохо работает. (в математическом обосновании я не очень уверен).
Значит применяем PCA потом проецируем 1000 сэмлов на новый базис и 1001 тоже и так же ищем K ближайших только для размерности векторов например 100, а не N.

Можно так же применить не просто линейный поиск, а сделать дерево из 1000 элементов и всё будет искаться быстрее.
Но тут возникает проблема, по мере наполнения сэмплов в базу, получается что при каждом добавлении нового элемента в базу требуется перестраивать индекс дерева, а так же если мы используем PCA пересчитывать базис.

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