n개의 물체의 좌표와 그 크기가 주어졌을때, 서로 닿았는지 판단하는 알고리즘이 O(n^2)보다 좋은게 있나요?

예전부터 고민했는데, 잘 모르겠어서 이렇게 조언을 구합니다.

물리 엔진에서도 이미 다루어졌을법한 주제긴한데 찾아봐도 잘 나오지 않는지라..

물체의 모양은 정사각형, 직사각형, 원 셋중 하나로만 주어진다고 가정해도 좋습니다.