For the capstone project at the end of my graduate Data Science studies in late 2022, I needed an algorithm that would converge to something close to centroidal Voronoi tiling, while tiling contiguous areas that could be very irregular in shape.
AFAICT, Lloyd's algorithm would not work for tiling non-rectangular areas (please correct me if I'm wrong), which is unfortunate because Lloyd's is very fast. So I came up with a computational approach that, at least, seems to mimic the output of Lloyd's for rectangular areas, but also works for arbitrarily-shaped areas where I failed to run Lloyd's:
Here's an outline:
- assume the area being tiled is discrete, made of a fine square grid (pixels); the size of each pixel is much smaller than the size of the whole area
- start with the centroids in some arbitrary arrangement inside the area (assign them to random pixels)
- for each pixel in the whole area, calculate the "energy" imparted to it by the centroids
- the "energy" is proportional to 1/d, where d is the Euclidean distance between pixel and centroid (this is similar to physical fields such as gravity)
- for any given pixel, only the nearest centroid imparts "energy", all other centroids are ignored (this is unlike physical fields)
- now apply simulated annealing, or some other optimization algorithm, to maximize the total "energy" of the pixels, as a function of the coordinates of the centroids within the area
- for concave areas (or any area, really), centroids are constrained to the inside of the area
TLDR: The final centroid positions are found by maximizing a specific energy functional, iteratively.
(I'm probably abusing the term "centroid". In my application, they are user clicks on an image - I need to simulate clicks from human operators, and a true centroidal Voronoi tesselation would be an excellent simulation, where the centroids would be the simulated clicks.)
The algorithm is discrete, but I assume it can be extended to a continuous approach involving integrals.
More details:
Code:
https://github.com/FlorinAndrei/segmentation_click_train
https://github.com/FlorinAndrei/segmentation_click_train/blob/main/uniform_clicks.py
Experimenting with the code on rectangular areas, it is reliably converging to tesselations that look very similar to the output from Lloyd's algorithm. But it also works with arbitrarily-shaped areas, and the results are visually similar.
My experience in this field of mathematics is marginal, my background is Physics and Data Science. I assumed that the code converges to a centroidal Voronoi tiling, where applicable, but I have no proof for it.
My questions are:
Can it be shown, or disproved, that this algorithm converges to a centroidal Voronoi tiling, at least for rectangular areas?
If it does converge, then can it be reasonably said it "generalizes" CVT to arbitrarily-shaped areas?
Thank you.
