Summary: A new polygon decomposition problem, the anchored area partition problem, which has applications to a multiple-robot terrain-covering problem is presented. This problem concerns dividing a given polygon \(\mathcal P\) into \(n\) polygonal pieces, each of a specified area and each containing a certain point (site) on its boundary or in its interior. First the algorithm for the case when \(\mathcal P\) is convex and contains no holes is presented. Then the generalized version that handles nonconvex and nonsimply connected polygons is presented. The algorithm uses sweep-line and divide-and-conquer techniques to construct the polygon partition. The input polygon \(\mathcal P\) is assumed to have been divided into a set of \(p\) convex pieces \((p=1\) when \(\mathcal P\) is convex), which can be done in \(O(v_{\mathcal P}\log\log v_{\mathcal P})\) time, where \(v_{\mathcal P}\) is the number of vertices of \(\mathcal P\) and \(p=O(v_{\mathcal P})\), using algorithms presented elsewhere in the literature. Assuming this convex decomposition, the running time of the algorithm presented here is \(O(pn^2+vn)\), where \(v\) is the sum of the number of vertices of the convex pieces.