1
$\begingroup$

Question: Given a convex n-gon P. How can we efficiently find the partition of P into 2 pieces with areas in the some given ratio $t : (1-t)$ where $0<t<1/2$ such that the length of cut is minimum?

Remarks: The question of dividing P into 2 pieces with the outer perimeter of P divided in the ratio $t : (1-t)$ where $0<t<1/2$ with least cut length is much simpler - the shortest cut is necessarily a straight line and an O(n) algorithm can find it (one of the pieces can be degenerate but that seems okay). However if it is the area that is being partitioned (present question), then the shortest cut could be a circular arc and finding it seems harder.

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .