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 oenter image description heref graph, computational geometry and mathematics.


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.