###
Sweepline Redistricting

The redistricting schemes we consider throughout this article are primarily concerned with equal populations and compact districts. For definiteness, consider the state of Washington with 9 legislative districts–the number of districts it had just prior to the 2010 census. Washington currently has 10 congressional districts, but 9 factors nicely and hence provides a better illustration of the concept. It is clear that there are a number of different ways to partition the state into regions with equal population. This paper will discuss two methods each of which can be adapted to provide a multitude of equal partitions.

In this section, we borrow a term from the mathematical literature of Voronoi tessellations [Okabe]. Some methods of generating Voronoi tessellations rely on an imaginary line that sweeps from left to right across a plane. When the line meets certain conditions, geometric events are generated that ultimately lead to a Voronoi diagram [Fortune].

Our first equal partitioning scheme borrows from this idea. We start with an imaginary vertical sweepline at the left most edge of the state of Washington. We sweep from left to right across the state. When the line has swept out a certain portion of the population, it leaves a copy of itself there marking the boundary of a region and continues on to sweep out the next region.

In an effort to draw 9 equal population districts as in this figure, a vertical sweepline first divides the state into three equal population regions. Subsequently, in each of the three regions, a horizontal sweepline divides the region into three equal population subregions. The result is 9 rectangular regions of equal population.

**A sweepline redistricting of Washington state. Each of the 9 regions has equal population.**

Notice in the figure that the second vertical partition is quite narrow. This results from the fact that it contains the densely populated Seattle-Tacoma area. While having equal population, these districts are not compact. They tend to be long and skinny instead of stout and blocky.

To emphasize the non-uniqueness of such partitions, imagine starting first with a horizontal sweepline and then generating subregions using vertical sweeplines. There would be 9 equal population districts, but they would be different from those pictured here.

How do we generate districts of equal population that are also compact? We move to another idea from the literature of Voronoi tessellations--that of sweepcircles.