Method and system for fast approximate region bisection

Abstract

Methods and systems in accordance with the present invention automatically subdivide an area having an arbitrary shape into multiple sub-regions that have approximately equal area under a threshold, with compact shapes having minimal perimeter length. These systems input an arbitrarily shaped zone and recursively bisect it until all of the new sub-zones are smaller than a particular threshold. A data processing system subdivides a two-dimensional region, such as a digital image of a landmass. The data processing system loads the region into memory, determines a minor axis of the region, and splits the region along the minor axis into a first sub-region and a second sub-region. The sub-regions are evaluated to determine if they are under the threshold area. The steps of the process are repeated until all resulting sub-regions are under the threshold area. Consistently compact sub-regions with minimal perimeter are achieved by splitting along the minor axis.

Dependencies are inferred from the claim text.