Дано множество окружностей (возможно до нескольких тысяч), дана точка. Нужно определить в какую окружность попадает точка.
Нужен алгоритм быстрого поиска, не простого перебора. Как впихнуть сюда хэш-таблицу я не представляю, поэтому она отпадает. Остается бинарное дерево, но как его организовать? Какую окружность пихать влево, какую вправо?
У окружностей может быть разный радиус, располагаются абсолютно хаотично, точнее нет какой-то определенной системы.
Жду советов, заранее спасибо.

Ну вообще, несколько тысяч окружностей можно и так проверить. Это не так уж и много. Зачем вам оптимизация? Насколько часто вам необходимо проверять принадлежность точки одной из окружностей?

Переведите координаты центров в полярные (желательно ещё и начало координат сместить в центр масс) и отсортируйте по длине вектора или углу вектора. То же сделаете и с целевой точкой. Станет намного легче.

Да забыл, программа для ембедед устройства, ресурсы которого естественно намного меньше компьютерных. Проверяться будет не реже одного раза в секунду.

Интересно, попробуем погуглить.
Кстати координаты gps.

Это сообщение отредактировал(а) Homer - 12.1.2010, 16:09

А набор окружностей - статический? иными словами, можно ли провести "артподготовку" этого массива окружностей для удобного поиска?

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

Построй простой пространственный индекс: разбей пространство сеткой квадратов на кластеры, в каждый кластер помести ссылки на все круги, которые его пересекают. Дальше ищи только в том кластере, куда попадает точка. Размер сетки подбирается органолептически - чтобы пустых кластеров было мало, но в каждом кластере было не слишком много объектов.
Если объекты распределены сильно неравномерно, то можно подумать о более сложной структуре - древовидной. Но она требует больше ресурсов как при вычислении, так и памяти.

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

Поэтому удобней применять не такие прямые методы, а всякие методы, как в предыдущих постах. Можно каждый круг описать квадратом, потом выполнить запрос на поиск всех квадратов, содержащих данную точку (а это значительно проще, чем для случая кругов), а потом уже "вспомнить", что мы вообще-то искали круг, т.е. перебрать все найденные квадраты и проверить, попадает наша точка в их круги или нет. Теоретически, в худшем случае, первая фаза алгоритма могла выдать все квадраты, хотя круги на самом деле точку не покрывают. Так что этот алгоритм будет работать за O(N) в худшем случае, но в реальных случаях обычно гораздо быстрее.

Самый простой способ осуществить запрос на поиск квадратов: рассмотрим все иксы вершин квадратов, отсортируем, и будем рассматривать по два соседних (в порядке сортировки) икса: X_i и X_{i+1}. Область между этими двумя иксами - это вертикальная полоса. Заранее для каждого i сделаем список квадратов, которые попадают в эту полосу. Тогда, когда поступает запрос в виде точки P(PX,PY), надо сначала за O(logN) (бинарным поиском) найти i, т.е. вертикальную полосу, в которую попала наша точка, а потом за O(logN)  (тем же бинарным поиском) уже поиском внутри вертикальной полосы найти один квадрат, лежащий на точке (PX,PY), ну а потом двигаясь по полосе, за O(количества_квадратов_в_ответе) получить список всех квадратов, покрывающих точку. Итого асимптотика поиска O(logN + количество_квадратов_в_ответе), но достаточно большие затраты на предобработку и память: O(N^2). Если это не устраивает, есть и лучшие алгоритмы, с меньшим потреблением памяти.

maxdiver, этот метод был наш основной вариант Но в итоге решили использовать квадродерево, приблизительно то же самое что предлагал Earnest. При инициализации выполняется разбиение на четыре участка от средней точки, потом эти участки так же разбиваются и тд до заданного уровня детализации, в последних секторах хранится список всех окружностей входящих в него, которые затем и проверяются на попадание точки. Т.о. алгоритм поиска довольно прост, сравниваются только координаты точки с координатами средней точки текущего узла дерева и определяется следующий сектор.
Наверное, этот алгоритм оптимальный для данной задачи, так что, думаю, решение найдено. Всем спасибо.