TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Friday, January 01, 2010

Congruent Partitions - A Special Case

Question: Let us say, we cut from a convex polygon P 2 mutually congruent pieces such that the pieces have as great an area as possible. Find that polygon P which causes the maximum wastage - the fraction of the area wasted to the total area of P.

P is constrained to be convex with the pieces allowed to be non-convex. Which shape of P gives highest 'wastage fraction'? Basically, we need to upper-bound the wastage fraction when a convex P is 'maximally congruent bisected'.

A simple fact: The two maximum area pieces have to touch each other; indeed, otherwise both pieces could be moved in the interior of P (which is convex) to a config where neither piece touches the walls of P or each other - and from that stage, both pieces can be expanded identically => the area of the pieces were not max to begin with.