Connected Area Partitioning
Susan Hert · Max Planck Institute for Plasma Physics · 2001
We present an algorithm to solve the following polygon partitioning problem, which is motivated by a terrain-covering application in robotics: Given a simply connected polygon $\\cal P$ and values \\subrange{a}{1}{p+1} such that $\\sum_{i = 1}^{p+1} a_i = Area({\\cal P})$, find a partitioning of $\\cal P$ into $p+1$ polygons \\subrange{P}{1}{p+1} such that $Area(P_i) = a_i$ for all $i$ and polygon $P_{p+1}$ is connected to each of the other polygons. The algorithm we present runs in $O(n + q \\log q + pn)$ time for a polygon with $n$ vertices that has been partitioned into $q$ convex pieces.