DBSCAN
Also: density-based clustering, density-based spatial clustering of applications with noise
Given a radius ε and a minimum count minPts, points with at least minPts neighbors within ε are core points; clusters are chains of core points plus their border points, and the rest is noise. It finds arbitrarily shaped clusters without being told k.
Example
With ε = 0.5 and minPts = 4, two interleaving crescent shapes come out as two clusters, while a few scattered points far from both are marked noise; k-means would cut the crescents in half.