Vacation experiments with clustering algorithms.
Based on Accelerating Exact k-means Algorithms with Geometric Reasoning.
On iPhone 4 clusters up to 5000 annotations reasonably well.
Drawback: K-Means requires initial guess points.
On iPhone 4 clusters up to 3000 (on 4000 - noticeable delays appear) annotations reasonably well. Scales badly but good appearance compared to that of kingpin and Algorithm 1.
Build a library including both algorithms as "clustering drivers".