TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Monday, November 25, 2024

Partitioning a Convex Island into Convex Regions

Background:
1. This paper discusses the problem of partitioning a convex polygon C into n convex pieces such that each piece has equal area and equal length of the boundary of C: basically to divide a convex cake into convex pieces of same area and same amount of icing per piece.

2. Our 'fair partition' (spicy chicken) question (2006), a departure from the above, asks for partition of planar convex region C into n convex pieces all of same area and perimeter. It was proved by Avvakumov, Akopyan and Karasev (https://arxiv.org/abs/1804.03057) that such partitions do exist for all C's and all n.

Now, let us record a variant of the question that lies somewhere between the above two:

Given a convex planar region C to divide it into n equal area convex pieces such that each piece has the same length of cut. Basically, to partition a convex island into n convex parts, with equal length of wall needed by each piece - the coast needs no walls or fortification. And some of the portions could be landlocked - not have any coastline.

Remarks: I gather that the existence proof of the fair partition question (mentioned above) also guarantees the existence of a solution to the new question. Initially, there was some doubt as to the case where C is a convex polygonal region - ie not strictly convex but now, it seems clear that the cut length of each piece in a partition will evolve continuously with the piece itself and that the proof can handle it. So, it appears that this new variant is not really much of an issue. Still, I am keeping this post.

0 Comments:

Post a Comment

<< Home