I have run $k$-means on a large set of high-dimensional data, and now I want to find the distance from a point $x$ to the Voronoi cell associated with one of the $k$ centroids. (In a previous version of the question, I called this cell a "cluster", but that terminology might be confusing since one might think of a cluster as simply a set of points in the dataset.)
Can this be done efficiently? If not, can I efficiently approximate it? If I actually need the distance from the point to all $k$ Voronoi cells, is there anything faster than just running the point-to-cell distance computation $k$ times?
Also, I am not wedded to $k$-means. Actually, the question could be interesting for many types of clustering, and I would love to know about others too!