Вариантов на самом деле немало.
Но предложу такой. Разбейте плоскость, где они двигаются, на квадраты. Размер квадрата равен радиусу самой большой окружности (ну или с запасом, как хотите). И тогда вам достаточно проверять не пересечения всех со всеми, а пересечение каждой с окружностями, которые находятся в этом и в соседних квадратах.
Естественно надо обновлять содержимое квадратов каждый шаг, но это не самая затратная операция.
Ну и для проверки пересечений используйте не расстояние, а квадраты расстояний/радиусов - будет быстрее (хоть на сложность алгоритма и не повлияет)