Consolidate annotations on a zoomed MKMapView

Question

There are a number of bad ways to go about what I want to do, but this seems like one of those cases of "there must be a better way".

I am using an MKMapView in an iPhone app that displays a number of annotations. Pretend for conceptual discussion that each town in a US state has an annotation, so there's a fairly dense pile of annotations onscreen. As the user zooms out the map, those annotations start to crunch in on one another, until they are overlapping and become hard to pick out individually.

What I'd like to do is, at a particular density of annotations (say when any annotations overlap), consolidate those annotations into a single annotation that indicates it encloses a number of sub-annotations (some visual indicator to say, "zoom in and you'll see more annotations").

I could call CGRectIntersectsRect on the annotation views, but using that would appear to be an N^2 problem -- I would have to iterate over each annotation for each annotation. Consider this pseudocode:

FOR firstAnnotationView IN allAnnotationViews
   FOR secondAnnotationView in allAnnotationViews
       IF CGRectIntersectsRect(firstAnnotationView.frame, secondAnnotationView.frame)
           // found two overlapping annotations, consolidate them
       ENDIF
   ENDFOR
ENDFOR

You can see why that would be slow, and it would have to run every time the map was zoomed in or out!

So how would you all detect overlapping annotations in the map, and in a performance-savvy fashion, consolidate them intelligently?