Предположим, что у меня есть 1 миллион произвольно сформированных, произвольно ориентированных N-мерных эллипсоидов, случайно разбросанных по N-мерному пространству. Учитывая подмножество эллипсоидов, я хочу «быстро» определить множество всех эллипсоидов, которые пересекают эллипсоиды из первого множества.Быстрый алгоритм пересечения эллипсоида (ов)
Для этого должен быть алгоритм. Что это? В чем заключается сложность «O»?
Сложность «O» страдает от проклятия размерности, если вы разрешаете N-мерные данные. (Подробнее об этом см. В разделе this wikipedia article). Я рекомендую заимствование от симуляции физики и разделив эту проблему в «широкую фазу» и узкую фазу:
Узкая фаза - простая задача вычислительной геометрии испытаний для пересечения между произвольными эллипсами. Для широкой фазы вы захотите использовать пространственную структуру, такую как пространственный хеш, пространственное дерево (R-дерево, Kd-дерево, X-дерево, UB-дерево и т. Д.) Или заданную структуру ad-hoc некоторые специальные свойства данных, которые вы загружаете (например, несбалансированное дерево или хэш).
Текущий популярный метод - это дерево 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 или векторные intrinsics в C/C++ - не уверены, на каком языке вы работаете.
Для большинства данных сложность O (без учета проклятия размерности) должна быть приблизительно амортизирована O (m log n) для запросов (после создания дерева), где m - количество эллипсов в наборе запросов, а n - количество эллипсов в наборе данных.Построение самих данных не должно быть хуже, чем O (n log n). Умножьте все на Exp (d), где d - размерность - так оно и происходит с такими вещами.
Увлекательный! Спасибо за вход. Таким образом, мое сообщение о переносе - это то, что если я могу сделать некоторые предположения о максимальном размере эллипсоидов, тогда я могу использовать Kd-дерево, чтобы быстро отбирать пространство до размера, который более управляем для задачи вычислительной геометрии грубой силы , – JnBrymn
По существу да. И если вам действительно нужно из-за ограничений по пространству, вы можете сделать это с диска, поскольку обход дерева намного меньше, чем в перекрестном режиме. Но хорошо оптимизированное решение грубой силы (если дело доходит до этого из-за требований, о которых я не знаю) все еще может работать. Я на самом деле отправил игры, которые грубо заставляют подобные проблемы в течение нескольких миллисекунд за кадр, но это была очень тщательная оптимизация. – Kaganar
Если вы не хотите использовать предварительно свернутую реализацию Kd-дерева и вместо этого предпочтете использовать свою собственную структуру, если эллипсоиды имеют довольно согласованный размер, пространственная структура хэша намного проще реализовать и может иметь несколько улучшенных в зависимости от самих данных. Kd-деревья обычно более агностичны для данных, но более сложные операции замедляют их. Оба они очень чувствительны к размерности. – Kaganar
Почему? Без причины, это пахнет «сделайте мою домашнюю работу для меня». – spender
Можно ли предположить, что ваши эллипсоиды хранятся в виде древовидной структуры данных, такой как N-мерный эквивалент квадратного дерева? Если нет, то это в значительной степени проблема * O (MN) *, где * M * - размер подмножества, а * N * - размер набора. –
@spender - отлично! Это означает, что ответить будет легко. Почему это потому, что я хочу связать произвольные распределения вероятностей с использованием семейств сфер. Определение того, какое семейство сфер перекрывается, позволит мне сделать первый разрез при решении обобщенной проблемы правдоподобия. - Нет, это не проблема домашних заданий. – JnBrymn