# Efficiently find the distance from a point to the decision boundary for assigning points to a particular $k$-means cluster

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!

• About the second problem: notice that in $d$ dimensions, it takes at least $d$ distances between an unknown point and known points to locate the former. So you must compute at least $d$ distances, making the problem $\Omega(d^2)$.
– user16034
Sep 29, 2022 at 15:11
• Hi, I'm not sure which problem you mean by "the second problem", but in general I don't understand how this observation about locating unknown points implies anything about my problem(s). If $k=2$, for example, you could just explicitly compute the decision boundary and figure out the distance to it and which side the point is on in a constant number of operations with complexity $O(d)$.
– gmr
Sep 29, 2022 at 16:04
• I am commenting on the existence of a shortcut to computing the $k$ distances.
– user16034
Sep 29, 2022 at 16:09
• – gmr
Sep 29, 2022 at 16:11
• A rough rule of thumb is: when the dimension $d$ is large, everything is hard and you're just hosed (for worst-case running time). So I don't hold out much hope for an efficient ($o(kd)$ time) answer to your question. When $d=2$, there are lots of clever algorithms.
– D.W.
Sep 29, 2022 at 17:04

If you want to compute distance to the closest (different) cluster, then problem is $$\Theta(kd)$$ as you just need to compute distance to $$k$$ hyperplanes. However, if you want to compute distance (of a point $$p$$) to a general cluster, you need to solve a Quadratic program (QP). Voronoi cell is a solution to a set of linear inequalities, say $$\{x | Ax \leq b\}$$. Then the quadratic program is: $$\min ||x-p||^2$$ $$s.t. Ax \leq b.$$
• Thanks! This makes a lot of sense. Unfortunately, I don't have any experience with convex QP. I spent some time Googling, but I was still unsure what performance to expect (or even whether the problem is $O(kd)$) and what software package would be good. In my application, $k$ and $d$ are both in the range 100-1000.
• The performance of QP solvers varies a lot by the problem structure. E.g., if we expect just a few constraints to be active - as it is probably here - it could be beneficial to solve the dual problem via coordinatewise descent since the dual solution will be probably sparse. See en.wikipedia.org/wiki/Quadratic_programming for the dual problem. On the other hand, before implementign it yourself, you should probably try the available solvers (e.g., pypi.org/project/qpsolvers) With k,d = 1000 I would expect very roughly 0.1 sec per QP. The $O(kd)$ is not for QP.