An algorithmic approach to convex fair partitions of convex polygons

MethodsX. 2023 Dec 23:12:102530. doi: 10.1016/j.mex.2023.102530. eCollection 2024 Jun.

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. In this article we describe an algorithm that finds such fair partition. •The Fair Partitions method finds a fair partition for any given convex polygon and any given number of regions.•Our method relies on two well-known methods: Lloyd's algorithm and the Normal Flow Algorithm.•The method proposed in this article can be used in various contexts and many real-world applications.

Keywords: Centroidal Voronoi partition; Convex Fair Partitions Algorithm; Convex equipartition; Fair partition; Lloyd's algorithm; Voronoi partition.