Сложность "O" страдает от проклятия размерности , если вы допускаете N-мерные данные. (Подробнее об этом см. в этой статье Википедии ). Я рекомендую позаимствовать физическое моделирование и разделить эту проблему на «широкую фазу» и узкую фазу:
- Широкая фаза консервативно находит существенно меньший набор пар потенциально перекрывающихся эллипсов.
- Узкая фаза обрезает множество потенциально перекрывающихся пар эллипсов до тех пар, которые действительно перекрываются.
Узкая фаза - это простая задача вычислительной геометрии проверки пересечения между произвольными эллипсами. Для широкой фазы вам нужно использовать пространственную структуру, такую как пространственный хеш, пространственное дерево (R-дерево, Kd-дерево, X-дерево, UB-дерево и т. Д.) Или специальную структуру, заданную некоторые специальные свойства загружаемых данных (например, несбалансированное дерево или хэш).
В настоящее время популярным методом является Kd-дерево. Существует множество документации и уже закодированных версий дерева Kd, которые легко настраиваются, поэтому я рекомендую вам посмотреть онлайн. (Google ваш друг в этом.) Преимущество использования большинства древовидных структур состоит в том, что если набор, с которым вы ищете пересечения, относительно компактен, вы можете искать по дереву только один раз и находить пересечения без необходимости выполнять несколько обходов дерева. , Это поможет с шаблонами доступа к кешу (будь то из основной памяти или с диска). Тот же алгоритм может обрабатывать разрозненные однотипные запросы. Однако, вероятно, вы выполняете работу, которая значительно выиграет от свойств компактного набора запросов.
Kd-дерево не решит ваши проблемы для всех эллипсоидов - например, если у вас есть эллипсоид размера N, чья основная ось от (0, 0, 0, 0, ...) до (1) , 1, 1, 1, ...), но с небольшими или несущественными вторичными осями (и впредь не сильно пересекающимися) все равно потребуется узел, который покрывает [0,1] во всех N измерениях. Если ваши эллипсоиды попадают в [0,1] ^ n, то каждый эллипсоид будет проверяться на пересечение с вышеупомянутым неудобным эллипсоидом. Тем не менее, с данными реального мира (и даже наиболее синтетическими, если вы не очень стараетесь замедлить Kd-деревья), подход Kd-tree должен быть выигрышным.
Если вы ожидаете, что Kd-дерево будет успешным для эллипсоидов в тысячном измерении, скорее всего, вам лучше с помощью поиска методом грубой силы. (Вышеупомянутое проклятие размерности.) Однако ...
Миллион записей не так уж и плох, если у вас есть оптимизированная реализация, но если вы делаете много запросов (миллионы), это будет медленно (порядка 10 секунд или хуже). Однако я видел несколько удивительных цифр из хорошо оптимизированного векторизованного кода. (Даже поставлял некоторые продукты с использованием этой стратегии.) При правильной когерентности кэша перебор будет занимать не более миллисекунд. Это означает либо ASM, либо векторную встроенность в C / C ++ - не знаю, на каком языке вы работаете.
Для большинства данных сложность O (без учета проклятия размерности) должна составлять примерно амортизированную O (m log n) для запросов (после построения дерева), где m - количество эллипсов в наборе запросов, а n - количество эллипсов в наборе данных. Построение самих данных не должно быть хуже, чем O (n log n). Умножьте все на Exp (d), где d - размерность - так оно и происходит с такими вещами.