# Balanced power diagrams for redistricting

**Vincent Cohen-Addad**

**Philip N. Klein**

**Neal E. Young**

**Date:** October 9, 2017

### Abstract:

We propose a method for redistricting, decomposing a
geographical area into subareas, called districts, so that the
populations of the districts are as close as possible and the
districts are compact and contiguous. Each district is the
intersection of a polygon with the geographical area. The polygons
are convex and the average number of sides per polygon is less than
six. The polygons tend to be quite compact. With each polygon is
associated a center. The center is the centroid of the
locations of the residents associated with the polygon. The algorithm
can be viewed as a heuristic for finding centers and a balanced assignment of
residents to centers so as to minimize the sum of squared distances of
residents to centers; hence the solution can be said to have low
dispersion.

**Full paper: https://arxiv.org/pdf/1710.03358**

**Code: https://github.com/pnklein/district**