How to perform spatial partitioning in n-dimensions?

Question

I am trying to create a Vector Quantization implementation as a C ++ template class that can handle various types and sizes of vectors (e.g. 16 byte dimension vectors or 4d doubling vectors, etc.).

I read the algorithms and I understand this:

here and here

I want to implement the Linde-Buzo-Gray (LBG) algorithm, but it’s hard for me to understand the general cluster separation algorithm. I think I need to define a plane (hyperplane?), Which splits the vectors in the cluster, so there is an equal number on each side of the plane.

[edit to add additional information] This is an iterative process, but I think that I start by finding the centroid of all vectors, then use this centroid to determine the plane of splitting, get the centroid of each side of the plane, continuing until I find the number clusters necessary for the VQ algorithm (iteration for optimization with less distortion along the way). The animation in the first link above shows this beautifully.

My questions:

What is the algorithm for finding a plane when I have a center of gravity?

How can I check a vector to see if it is on either side of this plane?

Answer 1

If you start with one centroid, you will have to break it down, basically by doubling it and slightly moving the dots in an arbitrary direction. A plane is a plane orthogonal to this direction.

But you do not need to calculate this plane.

More generally, region (i) is defined as a set of points that are closer to the centroid c_i than to any other centroid. When you have two centroids, each area is a half-space divided into a (hyper) plane.

How to check on vector x to see which side of the plane is this? (that with two centroids)

Just calculate the distance || x-c1 || and || x-c2 ||, the minimum value index (1 or 2) will give you in which area the point x belongs.

More generally, if you have n centroids, you must calculate all distances || x-c_i ||, and the center of gravity x is closest (i.e. the minimum distance) will give you the region x belonging to.

Answer 2

I do not quite understand the algorithm, but the second question is simple:

Call the V vector that extends from any point on the plane to a point in the question. Then the point in the question lies on one side of the (hyper) plane as normal N if V · N > 0