The Area Partitioning Problem

Abstract

Given an arbitrary polygon with $n$ vertices, we wish to partition it\ninto $p$ connected pieces of given areas. The problem is motivated by a\nrobotics application in which the polygon is a workspace that is to be\ndivided among $p$ robots performing a terrain-covering task. We show that\nfinding an area partitioning with minimal cut length is NP-hard in the number\nof pieces and that it is even hard to approximate to within any factor that\nis independent of the shape of the polygon.\nWe then present a simple $O(pn)$-time algorithm that produces\nnon-optimal, but often quite reasonable, area partitionings for arbitrary\npolygons.