Algorithm to equalize the area of random tessellation of various polygons

Question

I am looking for an algorithm that I can apply for a random tessellation of polygons with different areas. The algorithm can relax the geometry of the polygons to a condition that all of them would have the same area!

Someone should have faced this problem. The simplest case is that all the polygons have the same number of edges. In that case, one can find the relationship between the periphery and the area. However, the algorithm should work for general case with polygons with different number of edges.

I would appreciate if you guys give me some hints or link me to some related studies that might exist in the field of graph, computational geometry and mathematics.

Answer 1

The fairly simple Lloyd's algorithm can be used to achieve this.

The essence of the algorithm is you start with a given tesselation defined by a set of points and a distance metric.

The points are then moved to the centroids, allowing the tesselation and the areas to be recomputed. This iterative process is then repeated until the movement is sufficiently small. If you are familiar with k-means clustering from statistics/classification it is essentially the same process.