Is there an efficient way to discriminate space based on K-Means results? Suppose we done K-Means and got K centroids of clusters and we want to tag new points based on those K centroids. 
UPDATE: These K centroids are given to me, so I can't go for another clustering algorithm. Also I have a large number of 2d points and a big k, so it's very important to get appropriate complexity.
The solution came into my mind is to do:
For every p in newPoints do:
    For every c in centroids do:
        calculate distance between c and p
        if distance < minDistance
            minDistance = distance
            p.tag = c.tag
    end for
end for

But the complexity of this solution is O(K*N) where N is the number of new points.
I would like to know if there is a solution with less complexity.
 A: If you only want to tag points, the most efficient way would be to take the centroid a build a kd-tree with them. Just finding the nearest center has complexity O(log n). kd-trees are employed to perform nearest neighbours searches efficiently with a big number of applications.
There are actually variants of k-means based on kd-trees to improve performance, see for example "An Efficient k-Means Clustering Algorithm: Analysis and Implementation".
A: The only way that's faster than that is to set up that inner step so that it uses a hash search instead of a lookup, but those methods will not be exact (in fact I think that's provable). One easy way to implement that is to do the clustering hierarchically, but that won't necessarily give you the same set of clusters that you've got. However if the clusters are well separated it may be pretty close.
If you want to stick with the clusters you've got, basically you can get the same thing by hierarchically clustering your cluster centroids. Here's a simple example: say you have 4 cluster centers. Cluster those centers into two meta-clusters of 2, each with its own center. Then at tag time, first figure out which of the 2 meta-centers it's closest to, and within that figure out which of the remaining 2 centroids it's closest to. You could repeat this process to effectively have $\log K$ comparisons per data point rather than $K$.
The main issue with that approach is that it won't necessarily give you the same assignment as the lookup. For instance if your points were in $\mathbb{R}^2$ and you have like 10 different clusters, the partition boundary between two sets of clusters is almost certainly non-linear, but we'd be forcing it to be linear. If you were really concerned about edge cases like that, you could get fancy by saying if it was close to that border then to do a full search. 
So again, this wouldn't be exact but it would be $\mathcal{O}(n\log K)$ so if you have a lot of clusters it could be worth it. Also if the dimension of your data is as large as $K$ or nearly as large, the loss in exactitude here will be very small. 
