Item

Abstract

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.