Obstacles Aware Partitioning for Bounding Worst Case Response Time of Mobile Surveillance Fleet

When a fleet of mobile units is used for surveillance and response to potential events, the geographic area of interest is often partitioned into smaller regions, and a particular (subset of) unit(s) is assigned to each region. One of the main reasons is to put a bound on the travel time for a unit in charge of responding to a new event/request from the unit's current location to the location of the occurrence of that event. In practice, the area may contain obstacles (e.g., buildings that have to be circumvented by ground mobile units or no-fly zones in case of drones). Although the problems of navigating among obstacles and spatial partitioning have been studied in the past, in this work we take a step towards tackling the setting of partitioning a geographic area of interest with obstacles in it, for the purpose of bounding the worst-case response time to an event by a member of a fleet of mobile units. To this end, we introduce a novel data structure and present an algorithmic solution for its construction, enabling a distribution of a fleet of mobile units to disjoint regions of the area of interest in a manner that will ensure a bound on the worst case response time in each region. Our experiments over real and synthetic datasets demonstrate the benefits of the proposed methodology over adaptation of existing spatial partitioning techniques.