Intersecting Circles

Algorithm and Runtime

Form a pointset of all circle centers. Use a WSPD to find the closest pair of centers \(O(n\log n)\). Return disjoint if the distance between these points is > 1, non-disjoint else.

Correctedness

Disjoint circles

\(\iff\) all pairwise circle centers are > 1 dist apart (unit circles, r=1)

\(\iff\) the closest pair of points is > 1 dist apart \(\square\).