A general algorithm for convex fair partitions of convex polygons

Abstract

Abstract A convex fair partition of a convex polygonal region is defined as a partition on which all regions are convex and have equal area and equal perimeter. The existence of such a partition for any number of regions remains an open question. In this paper, we address this issue by developing an algorithm to find such a convex fair partition without restrictions on the number of regions. Our approach utilizes the normal flow algorithm (a generalization of Newton’s method) to find a zero for the excess areas and perimeters of the convex hulls of the regions. The initial partition is generated by applying Lloyd’s algorithm to a randomly selected set of points within the polygon, after appropriate scaling. We performed extensive experimentation, and our algorithm can find a convex fair partition for 100% of the tested problem. Our findings support the conjecture that a convex fair partition always exists.

Keywords

• Convex equipartition
• Fair partition
• Lloyd’s algorithm
• Voronoi partition
• Centroidal Voronoi partition