Spatial clustering with the constraint that all clusters have equal count I wish to perform a spatial clustering of scattered data that represents geographic locations of individuals in an urban area. Hierarchical clustering seems to work well, and I have successfully done this for the 100,000 data points in the set.
However, as an additional constraint/objective, we wish that the clusters have equal count.  That is, the city center would be a small area spatially, and the suburban areas would be large.
Is there a ready-made solution for this problem?
 A: This is not really a clustering task anymore. See: clustering is about discovering structure, but you are forcing formal constraints to be much stronger than the structure.
However, you can look at it from a different angle:
A structure that tries really hard to divide the data into non-overlapping, equally sized "bins" is a balanced tree. So you probably want a spatial tree such as the R*-tree. It will try to partition your data into equally sized partitions.
Now in particular for 2D point data, it is much easier to bulk-load the tree using STR instead of using a full R-tree. Plus, it will actually get you non-overlapping partitions that are also really of equal size. The regular R- and R*-trees will only do this within certain thresholds.
The general process you need is very simple (and this is the consequence of your "equal size" constraint!): Compute sqrt(k) when k is your desired number of partitions.
Sort your data by the x-axis, and divide it into sqrt(k) equally sized partitions. For each of these partitions, sort that part of the data by the y-axis, and divide it again into sqrt(k) partitions. Then you have sqrt(k)^2 = k partitions that have the same size and do not overlap. Plus, it take just O(n log n) time, and this way is much faster than hierarchical clustering.
