**The initial approach**

My approach is based on drawing a line between two centroids. If I find a point on this line that does

*not*get quantized to either of the centroids, I declare the two regions not neighbors.

In this figure, A and B are clearly neighbors, whereas C isn't. Testing is done using a binary search: I sample the middle of the line, check if that point gets quantized to A or B - if to B, then pick the halfway point from the middle to A, keep going until either a non-A or B point is found or 10 iterations have been done. Generally for most checks the algorithm stops at the first check (see A and C) only for the neighboring regions will all 10 iterations be computed.

Problem is, this doesn't work very well. Let's remove D:

Clearly, C now is a neighbor of A, but the straight line is not where the boundary between A and C is located. So much for that...

**The proper way**

I found the correct way of solving this problem by looking at how Voronoi diagrams are drawn by MATLAB: using Delaunay triangulation. Then using MATLAB functions, the lists of neighbors for the centroids can be found by calling delaunay, then TriRep, then the edges method on the resulting structure. Here is some sample code:

% create a quantizer

V = zeros(2,8);

V(:,1) = [ 0 0 ];

for n=2:8

V(:,n) = [ sin(2*pi*(n-1)/8) cos(2*pi*(n-1)/8) ];

end

figure;

voronoi(V(1,:),V(2,:));

tri = delaunay(V(1,:),V(2,:));

tr = TriRep(tri,V(1,:)',V(2,:)');

The resulting edges array can now be examined and turned into a list of neighbors for each centroid. This should scale to higher dimensions, but won't work for 1-D - but there, the neighboring quantizer region problem is trivial anyways. (Note, I have the Signal Processing Toolbox, so I'm not sure all those functions are in default MATLAB.)

So while my initial quick bit of code didn't work, it did cause me to think about the problem a bit more deeply and I learned a bit about computational geometry.