Clustering/Voronoi cell identification

General Usage
1

I’m thinking of the following problem. I have a set of points in the plane which have either been pre-selected or were obtained by a clustering method (i.e., K-means). I thus have an associated Voronoi partition of the plane using either the k-means points or the pre-selected points. Now, I have a new point and I want to identify which of the Voronoi cells it is associated with. In either case, is there a ‘‘fast’’ method for doing this, or must it be done by a computing all the distances and finding the minimum (i.e., making it a linear in time cost)?

2