Weighted Voronoi region algorithms for political districting

Political districting on a given territory can be modelled as bi-objective partitioning of a graph into connected components. The nodes of the graph represent territorial units and are weighted by populations; edges represent pairs of geographically contiguous units and are weighted by road distances between the two units. When a majority voting rule is adopted, two reasonable objectives are population equality and compactness. The ensuing combinatorial optimization problem is extremely hard to solve exactly, even when only the single objective of population equality is considered. Therefore, it makes sense to use heuristics. We propose a new class of them, based on discrete weighted Voronoi regions, for obtaining compact and balanced districts, and discuss some formal properties of these algorithms. These algorithms feature an iterative updating of the distances in order to balance district populations as much as possible. Their performance has been tested on randomly generated rectangular grids, as well as on real-life benchmarks; for the latter instances the resulting district maps are compared with the institutional ones adopted in the Italian political elections from 1994 to 2001. (C) 2008 Elsevier Ltd. All rights reserved.