Proportional Partition of Holed Rectilinear Region amongst Multiple URAVs

Our goal is to decompose an arbitrary pathwise continuous rectilinear polygon with holes into a fixed number of nonoverlapping pathwise continuous rectilinear open subsets. This goal involves two additional hard constraints – a. The area of each subset must equal an a priori value. b. The union of the closure of the subsets must be equal to the polygon itself. A soft constraint is that any edge that defines the closure of any subset measures ω units or more. We give a decomposition algorithm that satisfies these constraints. Our goal is motivated by a problem involving parallel utilization of multiple unmanned reconnaissance aerial vehicles (URAVs) with heterogeneous endurance characteristics and equipped with similar sensors with heterogeneous capabilities to conduct a photographic scan of regions with urban-like structures. We discuss our motivation in greater details.