I'm in the process of implementing this paper and I'm running into an issue with the process listed in portion V-A (page 5). Specifically, the paper mentions that I should store the distance from each cluster to its bounding hyperplanes.

Given that the hyperplanes are all defined for voronoi clusters and they are simply equidistant between two centroids. I assume there is an elegant mathematical solution for solving for d(x, H), where x is a point in a dataset bound on some side by hyperplane H. Assuming I already have the centroids that define that hyperplane, how would I go about calculating the distance from a point within one of those clusters to the hyperplane?

I'm not expecting a hand-fed answer, but this paper treats it as a trivial exercise, and I'm having difficulty implementing this aspect, upon which much of the paper relies. I started doing some trig style derivations, but I then was concerned that standard trig doesn't generalize to many dimensions. I am just really not sure where to start on this.

Outside of this paper, I suppose the definition of the problem would be:

Given centroids C1 and C2, and a a point x Determine the distance between point x and a hyperplane equidistant from points C1 and C2

Any help would be hugely appreciated.


The base point to be used in the hyperplane can be $$ C = (C_1 + C_2)/ 2. $$ Next, we make a unit length vector, normal to the hyperplane, by $$ N = (C_2 - C_1)/ \parallel C_2 - C_1\parallel. $$ For some other point $X,$ the distance from $X$ to the hyperplane is $$ |(X-C) \cdot N| $$

You should draw some pictures; two dimensions is enough. We are in the $xy$ plane. Points $C_1 = (-1,0)$ and $C_2 = (1,0).$ The "hyperplane" is the $y$ axis. The fixed point is $C = (0,0).$ Finally, the normal is $N = (1,0).$ Suppose we have a new point $X = (3,5).$

  • 1
    $\begingroup$ Oh goodness. I was overcomplicating this tremendously. Thank you so much, it's been a long time since I actually did linalg. $\endgroup$ Dec 26 '14 at 3:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.