Ибо машинным способом определить налазят ли N объектов друг на друга потребудет от нас примерно N^2 операций.

С чего вдруг ? За O(N log N) она вполне решается. Диаграмма Воронова => Триангуляция Делоне => кандидаты на объединение...