opinion of using 'shortest splitline' algorithm for districting

[jimrtex]

It ignores any natural geographic features - it hops mountains and rivers in ways that ignore connectivity.

It splits existing political boundaries for counties and municipalities in ways that needlessly complicate elections and increase cost.

It tends to carve through major metro areas and if mapped at the level of whole census blocks it would appear just as ragged as some gerrymandered districts.

Unfortunately, the originator doesn't recognize these as weaknesses, but considers them features, since it avoids manipulation such as streets and mountains being moved.

It surrenders compactness for minimum line length.

This is more a matter of the particular algorithm that is used.  If stated as a goal of minimizing total bath length of internal boundaries, the districts would be compact.

It fails in any state subject to the VRA.

This proves the VRA is logically unsound.

[jimrtex]

This is more a matter of the particular algorithm that is used.  If stated as a goal of minimizing total bath length of internal boundaries, the districts would be compact.

The Shortest Splitline Algorithm is very precisely defined and can result in only one map.

It is one of a class of similar algorithms that have the objective of minimizing particular metrics.

[jimrtex]

Haha, oh wow, this algorithm really does hate keeping cities intact.

Medians are more probably to occur in areas of higher density.

The east-west median of population got stuck in the Detroit/Indianapolis area for 50 years or so, even as the mean continued moving westward.

[jimrtex]

Haha, oh wow, this algorithm really does hate keeping cities intact.

Medians are more probably to occur in areas of higher density.

The east-west median of population got stuck in the Detroit/Indianapolis area for 50 years or so, even as the mean continued moving westward.

True. The median is a point that only reflects how much of the data lies one either side of that point. The relative distance to that point does not matter, even though it would in the mean (or average). The median will either be at one of the data points or midway between two points if there are and even number of data points.

Since the median is located at a specific data point, the likelihood of it's occurrence is tied to the likelihood of finding any data point in general. That is the median is more likely to be at a part of the data set where data is more densely clustered. For the 2-D problem of the splitline algorithm, this means in areas of higher population density, ie cities.

In discussions about split line, one suggested alternative metric would be to consider density in the measure of the length of the cut line.  Lines that cut through less dense areas would be favored.

This is a pseudo-splitline.  I first sliced blocks into 11 equal-population slices based on longitude.  These were regrouped into a 3:4:4 pattern (based on less density to the west, and then resplit based on latitude.

http://www.redrawsf.org/

Click on View District Maps

Click on "Check 2010" map.

Be patient with the refreshes.  You can't interact while the map is repainting.  So when you zoom in, click on 3 or 4 steps up on the zoom bar, rather trying to drag the indicators.

[jimrtex]

In discussions about split line, one suggested alternative metric would be to consider density in the measure of the length of the cut line.  Lines that cut through less dense areas would be favored.

This is a pseudo-splitline.  I first sliced blocks into 11 equal-population slices based on longitude.  These were regrouped into a 3:4:4 pattern (based on less density to the west, and then resplit based on latitude.

http://www.redrawsf.org/

Click on View District Maps

Click on "Check 2010" map.

Be patient with the refreshes.  You can't interact while the map is repainting.  So when you zoom in, click on 3 or 4 steps up on the zoom bar, rather trying to drag the indicators.

The process makes more sense in an urban area where there is less variation in pop density. The uniformity in density shows up as districts that cover roughly the same amount of area. I'd still like to see this type of modified algorithm use the underlying street axes, so that the lines are less erose.

Think about if you sliced Illinois along a north-south axis into equal population slices.  In the north you would get extremely narrow slices running from Lake Michigan to the Mississippi.  You could then calculate a proportionality measure for each slice E-W length (average) / N-S width.

Find the narrowest slice and combine it with its narrowest neighbor, and calculate its proportionality measurement  ((E-W)/(N-S)) / magnitude.  Quit once the proportionality values are below some level (1.5?. 1.62?).

Repeat the process slicing east to west in the merged slices.  It might take another iteration in the Chicago area.

There was also a splitline done of San Francisco using election precincts, but it never made it out to the block level - 2010 block numbers are not the same as 2000 block numbers, and the precinct definitions didn't include all the zero-population blocks, and some precincts split blocks.

The boundaries still ended up being jagged.  California has some tight population limits for precincts, and there are requirements for polling places being within precincts. In high density areas, there might be precincts with 5 or 7 city blocks, so even when the street grid is regular, the precincts don't match the grid.

If I were implementing a splitting algorithm, I would try to partition near the center of area.  For example, for a given angle, find the cutline that would split the area into two equal areas, round to the nearest integer number of districts based on population, and find two cutlines parallel to the first.

If you try to split to equalize population, there can be corner cutting (see the first split in Illinois, which cuts across the outer fringes of the Chicago area.  Triangular area are less compact (total interior angle = 180 degrees, with smallest interior angle <= 60 degrees) and you can get some extreme needle-like districts.

If your cut line is more near the center, you will be more likely to not cut adjacent sides, and will introduce 4 new vertices with around 90 degree interior angles.

Perhaps even better is to do a 3-way partition using a modified 120-degree wye.  This would introduce 9 vertices with a total of 900 degrees, so could help keep the number of sides of some districts above 4.

[jimrtex]

IIRC you had a version some time ago where you took a splitline but then adjusted it to conform to the nearest county (or municipal) lines. This seemed to me like a preferable implementation of the concept since it corrects for political subdivisions while maintaining the core idea of splitline.

I'd forgotten that, but that was what had sparked my interest in splitline in the first place.

The way I oriented the cutline was to determine the minimum-area bounding rectangle around the area being divided, and then set the direction of the cutline perpendicular to the long axis of the rectangle.

I then divided the area (not the bounding rectangle) into two parts of equal area.  If the population of the two areas was X and Y; I found the two cut lines parallel to the first cutline that would divide the population into floor(X):ceil(Y) and ceil(X):floor(Y) and chose the one that produced the more equal division of area.

I then would adjust that cutline back and forth to get to a single split county.

But maybe the thing to do would be rather than finding the orientation of the cutline first, would be to choose the cutline orientation based on which angle left the fewest (net?) persons stranded on the wrong side of the county line:

For each trial angle (0 to 180- degrees)

   Find cutline that divides into equal areas.

   Adjust cutline so areas have population equivalent to integer number of districts, and
   and choose the one that creates the more equal area.

   Determine the population on each side of the cut line in counties that are split (modulo the
   district magnitude; since we can always create whole districts within that portion of the
   county*).

   For each subset of split counties, calculate the total population to the left of the cut line,
  and for the complementary subset, the total population to the right of the cut line.  In both
  cases modulo the district magnitude.  Take the absolute value of the difference.  This is the
  minimum number of persons that need to be split out of a single county.

  The quality of the cutline is the length of the original cut line times this stranded population.

end for each angle

For winning cut line, place all but one county one either side of the adjusted cut line, and split that county along a line parallel to the original cut line.

* An alternative method might be to apportion whole districts to larger counties (eg in Texas, apportion Harris 5, Dallas 3, Tarrant 2, Bexar 2, Travis 1, El Paso 1, Collin 1, Hidalgo 1), and in each of the counties distribute the residual population proportionately.   Then do a split line for the remaining 20 districts, and then refine the results.