I have a problem: I want to find a method which, given a set of centroids as x,y coordinates (the number of the centroids does not matter, more than one) it returns me a tessellation of the plane such that each region has the center of mass exactly at one of the given centroids.
It is similar to the Centroidal Voronoi Tessellation (CVT) (wiki, slides here, library here), yet I would like to generate it given the centroids, and not starting from the image and the number of centroids (as in the all other examples provided). Usually it is built by iteratively moving the centroids, while I would like to build it by iteratively growing the regions such that each centroid remains the centroid of each region.
If we grow the regions towards the center, they will touch each other. We can then stop one and continue the others, until we reach the end where we have (given $N$ starting centroids) $N$ regions, which do not have empty space between them (but can have empty space outside them, no need to fill a square).
Do you know of any algorithm capable of doing that or any idea on how to implement/get it to work?
PS: it may be an NP-hard problem.
Edit: I show an example image, in this case a handcrafted example:
So here, I created a grid on an empty plane, chose (randomly) some centers and created pieces (in this case regular symmetric polygon, which makes it easier for me) whose center of mass is exactly the center (highlighted in blue). But this is (slowly) made by hand. I am asking if there is a way to compute this systematically and with irregular shapes, without having the constraint of using only regular symmetric polygons! Can it be done using some modified version of the known tessellations (or maybe I missed the existing one doing already this?)
In this case I tessellated only a part of the plane, yes (@Ivan Neretin) it is not important. The target would be to have no space between the pieces (we are creating puzzles).