The Area Partitioning Problem
Hannah Bast, Susan Hert · 2000
Given an arbitrary polygon with $n$ vertices, we wish to partition it into $p$ connected pieces of given areas. The problem is motivated by a robotics application in which the polygon is a workspace that is to be divided among $p$ robots performing a terrain-covering task. We show that finding an area partitioning with minimal cut length is NP-hard in the number of pieces and that it is even hard to approximate to within any factor that is independent of the shape of the polygon. We then present a simple $O(pn)$-time algorithm that produces non-optimal, but often quite reasonable, area partitionings for arbitrary polygons.