Convex Equipartitions with Extreme Perimeter

Recomm. for undergrads: yes
Posted by: Nandakumar
on: October 22nd, 2015

To divide a given 2D convex region C into a specified number n of convex pieces all of equal area (perimeters could be different) such that the total perimeter of pieces is (1) maximized (2) minimized.

Remark: It appears maximizing the total perimeter is the easier problem.

Conjecture 1: It appears that for convex equipartition with maximum total cut length, the cut lines should not meet in the interior of C.

Conjecture 1a: for n=3, it appears conjecture 1 can be proved by proving the following subconjecture: If from a point P in the interior of C, three rays originate and divide C into three equal area pieces and if p_0 is the sum of the perimeters of the three pieces, then from at least one of the three points (call them A, B, C) where the three rays from P cut the boundary of C, there originate 2 rays which equipartition region C into three equal area pieces such that the perimeter sum of the three pieces is necessarily greater than p_0.

Conjecture 2: If conjecture 1 holds, one could have a greedy algorithm to achieve maximum perimeter sum as follows:

- From C, first cut out a convex region with 1/n of the total area such that the separating cut is the longest possible, then repeat the same process on the remaining piece and so on until we have n equal area pieces) appears to give the optimal answer

Generalizations: One could think of partitioning a convex regions into convex pieces with specified different areas and minimize/maximize the total perimter. Higher dimensional analgs too could be considered.


Online Reference (the only one known to the author): (*)

* indicates original appearance(s) of problem.