#algorithm #geometry #complexity-theory #computational-geometry
#алгоритм #геометрия #сложность-теория #вычислительная геометрия
Вопрос:
Допустим, у меня есть 1 миллион произвольно ориентированных N-мерных эллипсоидов произвольной формы, случайным образом разбросанных в N-мерном пространстве. Учитывая подмножество эллипсоидов, я хочу «быстро» определить множество всех эллипсоидов, которые пересекают эллипсоиды из первого набора.
Для этого должен быть алгоритм. Что это? В чем его сложность «O»?
Комментарии:
1. Почему? Без объяснения причин это пахнет «сделай за меня мою домашнюю работу».
2. Можем ли мы предположить, что ваши эллипсоиды хранятся в какой-то древовидной структуре данных, такой как N-мерный эквивалент четырехмерного дерева? Если нет, то это в значительной степени проблема с O (MN) , где M — размер подмножества, а N — размер набора.
3. @spender — отлично! Это означает, что ответ будет легко найти. Причина в том, что я хочу связать произвольные распределения вероятностей, используя семейства сфер. Определение того, какое семейство сфер перекрывается, позволит мне сделать первый разрез при решении обобщенной задачи о правдоподобии. — нет, это не проблема домашнего задания.
4. @Oli ДА! давайте предположим, что. Я пытался перефразировать проблему так, чтобы я мог использовать kd-дерево, но у меня ничего не вышло. В частности, я собирался описать 3D сферу как точку в 4D пространстве: (x, y, z, радиус). Но я сразу понял, что вы не можете использовать обычную метрику евклидова расстояния.
5. Суть проблемы в пересечении реальных эллипсоидов или в алгоритме разделения вашего 1 миллиона объектов на более разумное подмножество?
Ответ №1:
Сложность «O» страдает от проклятия размерности, если вы учитываете N-мерные данные. (Подробнее об этом см. эту статью в Википедии). Я рекомендую позаимствовать из физического моделирования и разделить эту проблему на «широкую фазу» и узкую фазу:
- Широкая фаза консервативно находит значительно меньший набор пар потенциально перекрывающихся эллипсов.
- Узкая фаза ограничивает набор потенциально перекрывающихся пар эллипсов теми парами, которые действительно перекрываются.
Узкая фаза — это простая задача вычислительной геометрии для проверки пересечения произвольных эллипсов. Для широкой фазы вы захотите использовать пространственную структуру, такую как пространственный хэш, пространственное дерево (R-дерево, Kd-дерево, X-дерево, UB-дерево и т.д.), Или специальную структуру, учитывая некоторые особые свойства загружаемых вами данных (например, несбалансированное дерево или хэш).
В настоящее время популярным методом является Kd-дерево. Существует множество документации и уже закодированных версий Kd-дерева, которые легко настраиваются, поэтому я рекомендую вам посмотреть онлайн. (Google — ваш друг в этом вопросе.) Преимущество использования большинства древовидных структур заключается в том, что если набор, с которым вы ищете пересечения, относительно компактен, вы можете выполнить поиск по дереву только один раз и найти пересечения без необходимости выполнять многократный обход дерева. Это поможет с шаблонами доступа к кэшу (будь то из основной памяти или с диска). Один и тот же алгоритм может обрабатывать разнородные запросы с элементами. Однако, вероятно, вы выполняете работу, которая значительно выиграла бы от свойств набора компактных запросов.
Kd-дерево не решит ваши проблемы для всех эллипсоидов — например, если у вас есть эллипсоид размерности N, основная ось которого находится от (0, 0, 0, 0, …) через (1, 1, 1, 1, …) но с маленькими или несущественными вторичными осями (и впредь пересекаются не часто) все равно должен быть узел a, который охватывает [0,1] во всех N измерениях. Если ваши эллипсоиды попадают в [0,1] ^ n, то каждый эллипсоид будет проверяться на пересечение с вышеупомянутым неудобным эллипсоидом. Однако с данными реального мира (и даже с большинством синтетических данных, если вы действительно не пытаетесь замедлить работу Kd-деревьев) подход Kd-tree должен быть выигрышным.
Если вы ожидаете, что Kd-tree будет успешным для эллипсоидов тысячи измерений, скорее всего, вам лучше использовать поиск методом перебора. (Вышеупомянутое проклятие размерности.) Однако…
Миллион записей — это не так уж плохо, если у вас оптимизированная реализация, но если вы выполняете много запросов (миллионы), это будет медленно (порядка 10 секунд или хуже). Однако я видел, как из хорошо оптимизированного векторизованного кода получаются удивительные числа. (Даже были отправлены некоторые продукты с использованием этой стратегии.) При правильной согласованности кэша перебор занял бы не более миллисекунд. Это означает либо ASM, либо встроенные векторные функции в C / C — не уверен, на каком языке вы работаете.
Для большинства данных сложность O (без учета проклятия размерности) должна быть примерно равной амортизированной O (m log n) для запросов (после построения дерева), где m — количество эллипсов в наборе запросов, а n — количество эллипсов в наборе данных. Построение самих данных не должно быть хуже, чем O (n log n). Умножьте все на Exp (d), где d — размерность — вот как это происходит с такого рода вещами.
Комментарии:
1. Увлекательно! Спасибо за информацию. Итак, мое выводное сообщение заключается в том, что, если я могу сделать некоторые предположения о максимальном размере эллипсоидов, тогда я могу использовать Kd-дерево, чтобы быстро сократить пространство до размера, который более удобен для решения задачи вычислительной геометрии методом перебора.
2. По сути, да. И если вам действительно нужно из-за нехватки места, вы можете сделать это с диска, поскольку обход дерева гораздо меньше зависит от пропускной способности, чем перебор. Но хорошо оптимизированное решение методом грубой силы (если дойдет до этого из-за требований, о которых я здесь не знаю) все еще может работать. На самом деле я поставлял игры, в которых подобные задачи решались методом перебора за несколько миллисекунд на кадр, но это была большая часть тщательной оптимизации.
3. Если вы не хотите использовать предварительно свернутую реализацию Kd-дерева и вместо этого предпочитаете использовать свою собственную структуру, если эллипсоиды имеют достаточно постоянный размер, пространственную хэш-структуру намного проще реализовать и она может иметь несколько более высокую производительность в зависимости от самих данных. Kd-деревья, как правило, более независимы от данных, но имеют более сложные операции, замедляющие их работу. Оба они очень чувствительны к размерности.