Connected Area Partitioning

Abstract

We present an algorithm to solve the following polygon partitioning\nproblem, which is motivated by a terrain-covering application in robotics:\nGiven a simply connected polygon $\\cal P$ and values\n\\subrange{a}{1}{p+1} such that $\\sum_{i = 1}^{p+1} a_i = Area({\\cal P})$,\nfind a partitioning of $\\cal P$ into $p+1$ polygons \\subrange{P}{1}{p+1}\nsuch that $Area(P_i) = a_i$ for all $i$ and polygon $P_{p+1}$ is connected\nto each of the other polygons. The algorithm we present runs in\n$O(n + q \\log q + pn)$ time for a polygon with $n$ vertices that has\nbeen partitioned into $q$ convex pieces.