I came across an analysis of California’s old redistricting process (which is still used for our U.S. congressional districts).

The Weakness of California’s Congressional Redistricting Criteria

This is why independent redistricting is so important. When legislators gerrymander to their advantage, it’s extremely difficult to prove it, and California courts are very reluctant to intervene.

I spent the past three days studying redistricting law including federal law, state law, the Voting Rights Act of 1965, and priorities among conflicting redistricting requirements.  These days of study have been immeasurably valuable for their clarification of requirements, because when it comes to redistricting, the redistricter has no right to change the law or disregard the law; it is imperative that the redistricter fully comply with existing law.  If a person doesn’t like the law and wants to change it, they can take their desire to the legislature or the courts, but changing the law is completely separate from the actual redistricting process.

So what did I learn?  Well, I already had a very comprehensive understanding of requirements for population equality, contiguity, compactness, respect for communities of interest, nesting of smaller district types within larger district types, and disregard for candidate residences and political party welfare.  What I hadn’t fully comprehended was the importance of race when it comes to redistricting.  I thought that an ideal redistricting plan is color-blind.  After much research, I found that I was wrong.  Color-blindness is not good enough.  Per the Voting Rights Act, a redistricting plan must be very mindful of race/ethnicity because a lack of awareness often disenfranchises minority voters.  A color-blind plan will often dilute the minority voice even if it isn’t intentional.  Even if there is no intent to dilute minority power, if there exists the effect of power dilution, the plan would be in violation of the Voting Rights Act.

I know that many will balk at this, because from a superficial perspective (as I previously had), it makes complete sense to be color-blind.  What becomes more apparent when researching the law and its history is that

1. there are many jurisdictions (not just in the South) that have a history of intentionally or unintentionally reducing a minority voter’s voting power to a level below that of a majority voter
2. when the minority voter’s voting power is maximized, it approaches and does not surpass the voting power of a majority voter

This leads to the following priority order among redistricting considerations:

1. population equality
2. race/ethnicity
3. contiguity
4. political geography (respect for boundary lines of cities, counties, etc.)
5. compactness
6. nesting (keeping two assembly districts in one senate district and ten senate districts in one board of equalization district)
7. disregard for candidate residences

What this means is that a consideration higher on the list will trump a consideration lower on the list.

Here is more that I learned about redistricting law:

• Concerning population equality, the difference between the highest populated district and lowest populated districts can be up to 10% as long as the reason for the discrepancy is not to disenfranchise.  If the reason is to respect communities of interest, there is no problem with discrepancies up to 10%.
• For the purpose of district population, the population count includes everyone including children and both legal and illegal aliens.
• For the purpose of the Voting Rights Act, counts refer to eligible voters only.
• In compliance with Section 2 of the Voting Rights Act, district lines must be drawn, if possible,  such that a minority group can make up the majority (> 50%) of the district to prevent cracking, yet should not be drawn such that they unnecessarily constitute more than 50% to prevent packing.  In compliance with Section 2 of the Voting Rights Act, a redistricter must consider:
  • Do minority voters represent most of the voters in a concentrated area?
  • Do majority voters tend to vote for different candidates than minorities?
  • Is the minority population otherwise protected given the “totality of the circumstances”?

  If the answer to the first two questions are yes and the answer to the third is no, the redistricting plan should not dilute.  This means that the minority group should be treated as a distinct voting group from that of the majority and that an effort needs to be made to ensure that this group’s political voice isn’t drowned out by that of the majority.

• While the purpose of Section 2 of the Voting Rights Act is progress for minority voters, the purpose of Section 5 of the Voting Rights Act is to prevent regression.  Multiple jurisdictions across the country have a history of disenfranchising minority voters.  These jurisdictions have additional restrictions on them when it comes to redistricting.  Most of these jurisdictions are states in the South, but in California, we have four counties that are subject to Section 5 restrictions.  These are Kings, Merced, Monterrey, and Yuba counties.  Per Section 5, any new plan can not put minorities in a worse situation than what they currently have.  To apply this standard, one must ask:
  • Is the new map intended to dilute minority voting power?
  • Does the new map have the effect of leaving minority voters worse off?

  What this means is that for jurisdictions that are subject to Section 5 restrictions, unless there is a mass exodus of minority voters, there must be at least as many minority districts as there have been in the past.  Once the district plan has been created for these jurisdictions, it must be submitted to the Department of Justice for approval before it can be put in place.  In practice, because the four California counties can not be properly analyzed in isolation, the district plan for the whole state must be submitted to the Department of Justice.

• Contiguity is a fairly simple requirement.  What isn’t strictly defined is contiguity with islands.  Some may say that an island is contiguous to the mainland where there exist ferry routes.  Others may say that an island is contiguous based on mainland proximity.  Still others may say that an island can be considered contiguous to any part of the mainland that borders on the same body of water regardless of distance.  There is no legal standard to the contiguity of islands.
• Districts must respect political boundaries, i.e., boundaries of cities, counties, neighborhoods, and communities of interest.  Note that this consideration is higher than the consideration for compactness and that if the political boundary has a non-compact shape, the district should have a non-compact shape.  “Neighborhood” is not strictly defined.  Sometimes cities define neighborhoods for their city.  There are also other sources for neighborhood data.  Frequently, data from one source does not conform with data from other sources.  Communities of interest are even less defined.
• Compactness is an interesting consideration.  While most researchers measure compactness based on the shape of the districts boundaries, even before I did my legal research, I didn’t think that made the most sense.  It is really population distribution that determines compactness.  The location of imaginary lines is irrelevant.  What is relevant is the set of people that comprise the district.  My legal research confirms my understanding.  The state of California defines compactness by population distribution of a district and not by the shape of the district.
• I had already known that two assembly districts should be nested in one senate district and that ten senate districts should be nested in one board of equalization district, but I had previously thought that this was a hard requirement.  My legal research revealed that this is among the lowest considerations when it comes to redistricting.
• Lastly, I had previously thought that redistricting data came solely from the census.  This isn’t true.  Most of it does come from the census, but a redistricter also uses electoral data to determine if minority voters in a district vote differently than majority voters, geographic data to determine what areas are urban versus rural, etc., and data directly from public testimony to determine what neighborhoods and communities of interest that voters feel that they are a part of.

So as you can see, there is a lot more to redistricting than what one might learn about it in a high school government class.  Computer algorithms can certainly still aid in the redrawing of district lines, but there are many more inputs and complexities than existing algorithms can handle.

Sources of information include:

• Voting Rights Act [wikipedia.org]
• Voting Rights Act of 1965 [wikisource.org]
• California Constitution, Article XXI [leginfo.ca.gov]
• Meeting of the Applicant Review Panel,
  February 25th, 2010 (video Segments 2 – 5),
  April 30th, 2010

I’ve spent most of the weekend so far poring over a ton of 2000 Census data—535 MiB of California data with a 637 page document to be more precise.  What was I trying to find out?

What is a community of interest?

Well, I already have a good understanding of the vague definition of the phrase.  Simply put, a community of interest is a self-identified social interest group.  Such a group can consist of members of a particular race, religion, sexual orientation, socioeconomic status, or lifestyle.  Ping pong players could identify themselves as a community of interest.  However, for a redistricting algorithm to respect communities of interest as the California Constitution requires, we need a much more precise definition of “community of interest”.  This is what led me to the census data.

For an algorithm to respect communities of interest, the algorithm needs data on that community of interest.  As far as I know, all data for redistricting comes from the census, and if your community of interest isn’t officially recognized in this data, there is no way for a computer algorithm (or a human being, for that matter) to objectively account for your community.  (Sorry, ping pong players.  If you’d like to be recognized for your lifestyle, you’ll have to lobby the census bureau to recognize you in the 2020 Census.)

What this does mean is that we do have a wealth of information about a surprisingly large number of communities.  These communities can be divided into two major categories:  geographic and demographic.

By using census data, a geographic community can be a:

• county
• county subdivision
• FIPS place (think: city or city equivalent)
• census tract
• block group
• block
• American Indian area
• American Indian trust land
• American Indian tribal subdivision
• metropolitan statistical area
• urban area
• ZIP code tabulation area (3 digit)
• ZIP code tabulation area (5 digit)

Demographic data includes:

• urban vs. rural
• race
• Hispanic/Latino vs. not Hispanic/Latino
• age
• sex
• household size
• household type
• family size
• family type
• group quarters
• housing owners vs. renters

(I summarized demographic characteristics into categories.  There are so many that I couldn’t even fit all the categories into a blog post.)

So there you have it.  A community of interest from the perspective of a redistricting algorithm can include any of the geographic and demographic characteristics above, as we have plenty of hard data for all of them.

Today I spent quite a bit of time reading news articles and listening to podcasts about the California redistricting commission.  Although there is certainly a lot of support for this much needed election reform, I was seriously shocked at how much fear, uncertainty, and doubt (FUD) was being spewed by some.  Many minority advocacy groups are saying that minorities are under-represented among the applicant pool.  Some people are saying that this process is too expensive.  Still others are saying that the commission will just lead to gerrymandering from a different source (citizens rather than legislators).

Pardon my language, but this is total BS.

There have been thousands of minorities that have signed up and there are 14 seats on the commission.  Clearly there are more minority applicants than seats, so there’s no reason to believe that minorities will be under-represented on the panel.  Who cares if any particular group is under-represented among applicants.  As a minority applicant, I don’t feel threatened.

California has set aside a few million dollars to support this redistricting process and is considering setting aside more.  It is certainly imperative that the process should be run as efficiently as possible, but the amount being spent is completely inconsequential compared to the billions that are lost on ineffective political campaigns, corruption, and waste due to our broken system.  Imagine how much is lost over a ten-year period.  The district plan set out by the commission will last ten years and the money being spent on it now will save a lot of money from waste over that time period.

As far as the commission engaging in gerrymandering of their own, I don’t see that as a likelihood.  I’ve read many of the applications, and based on the essay questions that I read, it truly sounds like the applicants’ sole goal is true election reform, not more of the same.  Among the many thousands of applicants, surely 14 impartial people can be found.  I think that this complaint is really just a last ditch effort by those in power to derail the reform so that they can maintain their power.

Lastly, I do acknowledge that people are susceptible to temptation, and there are forces out there that will certainly try to sway impartiality.  That is expressly why I promote redistricting by algorithm.  The redistricting process need not be 100% automated, but the closer to complete objectivity, the better, and using an algorithm to do as much of the process as possible would prevent gerrymandering.

Shameless plug:  If you support my concept of impartial redistricting by computer algorithm and wish to leave a positive, public comment supporting me as a potential commissioner, the applicant review panel would certainly like to hear from you.

As I mentioned before, I intend on writing implementations for some of the algorithms that I’m analyzing.  I believe that this will give me much deeper insight into the algorithms.  I started rolling my own Java GIS library as I don’t think it’s that complex, but today thought if there are already libraries out there, why re-invent the wheel?  I did some research and found that the two popular Java GIS libraries are OpenMap and GeoTools.  The tough part about choosing one is that both are supposed to be really good.  Both provide a lot of functionality, are well-documented, and come from actively supported projects.  I spent a fair amount of time trying to find out which one is better for me but still can’t lean toward one over another.  I feel like flipping a coin.

If anyone knows about the differences between these two libraries, give me a heads up.

The K-means algorithm is another algorithm proposed by University of Washington students.  Nate Bottman, Wes Essig, and Sam Whittle were recognized in the academic world for their proposal.  This algorithm shares a lot of qualities with the Voronoi diagram redistricting algorithm.

The algorithm works like this:

1. Distribute seed points throughout the state and associate all points throughout the state with the seed point that is closest to it.  These groups of points are unfinalized districts.
2. For each district, relocate the seed point to the population weighted center of the district, then re-associate all points to the closest seed point.
3. Repeat Step 2 until all districts are within tolerance levels.

There is a lot more math to it, but those are the basics of the algorithm.

The K-means algorithm - New York

Like Voronoi redistricting, the K-means algorithm isn’t completely objective because it requires a set of initial seed points as input.  The authors propose that this algorithm would excel if the desire is to keep districts in their approximate current locations with the intention of rounding out district borders, as seed points could be placed at the center of current districts.  I would agree that it would be useful for that scenario, but I’m not sure that would be an ideal goal.  I personally think that districts should be drawn without any regard for the districts previously drawn by legislators.  It feels way too subjective and open to abuse to me.  If there were already existing districts that had been drawn in an unbiased way, then I’m sure that K-means could be used to tune those districts upon the arrival of updated data but if that were the case, why not just use the unbiased algorithm from the past all over again?

The K-means algorithm produces ultra compact districts.  I can’t imagine how districts could be more compact.  Notice above how districts, particularly the geographically smaller ones have very rounded borders.

K-means is susceptible to concavities, but you’ll notice in the picture above that any concavities are very shallow.  This means that K-means has an outstanding district-to-convex-polygon ratio.

Lastly, if K-means seed points are placed in population peaks, the algorithm will result in districts that have a good respect for CCIs.

So how does this stack up to the other algorithms?  Overall, I still like the Voronoi diagram redistricting algorithm better, but I do like that the K-means algorithm shifts its district centers to coincide with population centers.  Perhaps a combination of the two might yield awesome results.  This is all just based on my best guess of what the results might be, as I haven’t gotten my hands on either algorithm implementation…   yet.

Ok.  So onto Voronoi diagram redistricting.  The gist of this algorithm is to distribute “generation points” throughout the state, then grow the districts from these points.  Each district’s boundaries grow at the same rate based on population.  Borders grow outward until no borders can expand any farther because they’re all touching neighboring districts.  Because they grow at a the same rate based on population, they’ll all stop growing at the same time which will be exactly when the whole state is covered, and they’ll all have the same population.  The University of Washington students who proposed this algorithm suggested manually placing the generation points using a heuristic.  Their heuristic is to place them on the highest population density points in the state as long as those points weren’t too close to each other.

Voronoi Growth

Let’s analyze the qualities of this algorithm as we did for shortest splitline.  As far as objectivity goes, this algorithm is less objective than shortest splitline because it’s not fully automated; it requires the generation points as input.  On the surface, this might seem like an issue, but I don’t think it’s as much of an issue as it may seem.  States generally have a limited set of highly populated cities and choosing the biggest cities as generation points should be fairly straight forward.  The bigger issue is when a metropolitan area is so populated that you have population density peaks right next to each other.  The authors suggest segmenting such an area off and redistricting it separately.

Voronoi diagram redistricting - New York

As far as compactness goes, Voronoi diagram districts are very compact.  If generation points are placed in reasonable places, you get more compact districts than shortest splitline.

Unlike shortest splitline, Voronoi districts are able to have concavities.  This makes its district-to-convex-polygon ratio lower than that of shortest splitline.

In my opinion, Voronoi districting’s biggest strength over shortest splitline is its respect for CCIs.  Because generation points are placed in the population center of cities, these communities are preserved in a single district.  Voronoi districting doesn’t take into account official city or county borders or physical terrain, but the respect for population centers is a big step forward.

Because of it’s strength and limited weaknesses, the Voronoi diagram redistricting algorithm is certainly one of my favorites.  It’s not perfect, and I’m confident that there are improvements that can be made, but I give it a big thumbs up.

Next up:  the K-means algorithm

So far I’ve done heavy research on two redistricting algorithms, and have spent many hours writing an implementation of one of those algorithms.  These two are the shortest splitline algorithm by Dr. Warren D Smith, a mathematician and researcher on election methods and a founder of the Center for Range Voting, and the Voronoi diagram redistricting algorithm by Sam Burden, Aaron Dilley, and Lukas Svec, University of Washington students and winners of the MAA Prize for the development of their algorithm.

Shortest Splitline

I started with my research and software development on the shortest splitline algorithm.  My reason for this is that when I was searching for what algorithms exist, this one’s name came up far more than any other.  I assumed that it was probably the best.

The basic concept of the algorithm is to take the entire state and iteratively split it in two based on population until you have the number of districts desired.  Each split uses the shortest bisecting line possible.  More precisely, the algorithm is to:

1. Start with the boundary outline of the state.
2. Let N=A+B where A and B are as nearly equal whole numbers as possible. (For example, 7=4+3.)
3. Among all possible dividing lines that split the state into two parts with population ratio A:B, choose the shortest.
4. We now have two hemi-states, each to contain a specified number (namely A and B) of districts. Handle them recursively via the same splitting procedure.

I mean no disrespect to Dr. Warren as he has contributed so much to the cause of better election methods, but based on my research, shortest splitline isn’t good enough for real world use.

Maybe I should start out by listing what I consider good qualities of a redistricting algorithm.  (If anyone has any other criteria, I’d love to hear about it.)

First and foremost, the algorithm should be objective, requiring little if any human decision making.  This should be pretty obvious.  Shortest splitline excels here as it’s entirely automated.

The algorithm should result in districts that are compact, meaning that points within the district should be fairly close to each other.  Shortest splitline results in lots of triangles and quadrilateral which are fairly compact.  Circles would be optimally compact, but the polygons that shortest splitline produces are WAY better than the monstrous districts that gerrymandering legislators come up with.

The algorithm should result in districts that have a low district-to-convex-polygon ratio.  What this means is that if you stretched a giant rubber band around the district, the district would fill the rubber band nicely.  If the district were in the shape of a zigzag or a ‘C’ that wouldn’t be the case.  The shortest splitline algorithm is optimal when it comes to its district-to-convex-polygon ratio because its districts contain no concavities.

Next (and this one is debatable), the algorithm should result in districts that respect communities of common interest (which I’ll abbreviate as CCIs from now on).  Shortest splitline doesn’t respect CCIs at all.  In many cases it draws lines directly through them.  Some would say that CCIs should not be respected because that violates the objectivity of the algorithm and provides an opening for gerrymandering.  While objectivity and CCI-respect certainly can compete with each other, I personally think that they don’t compete in all instances and there exists a good balance between the two objectives.  Regardless of whether one thinks CCIs should be respected or not, for implementation of California’s Voters FIRST Act, that respect is required by the California Constitution.

Article 21, SEC. 2. (d)(4) The geographic integrity of any city, county, city and county, neighborhood, or community of interest shall be respected to the extent possible without violating the requirements of any of the preceding subdivisions. Communities of interest shall not include relationships with political parties, incumbents, or political candidates.

Lastly, and most importantly, the shortest splitline algorithm is unusable because its district lines are straight.  Straight lines make for a beautiful looking map, but how are all the people whose homes sit on the border supposed to know what district they belong to?  Ivan Ryan contributed an implementation of the algorithm.  How his implementation works is it takes a large bitmap image of the state, calculates the population per pixel using census data, then draws boundaries using this pixel-level abstraction.  The result is a beautiful map, but there’s no meaningful way for a household to know what pixel it is mapped to.

After realizing that shortest splitline is unusable, I stopped writing my own implementation and decided to do a lot more research on other algorithms.

Next post:  Voronoi diagram redistricting! 

UPDATE: After thinking about it more, I retract my criticism of shortest splitline’s straight lines.  While it’s still true that straight lines are infeasible, the centroid of a census block can be determined and the entire census block can be within the district that the centroid is in.  This will make the lines straight at a macroscopic level while being usable at the street level.  I still maintain that the algorithm is incompatible with the California Constitution due to the lack of respect for CCIs.

Welcome to my new blog.  I’m a software engineer in Southern California and have taken an interest in coming up with technical solutions to gerrymandering.  Specifically, I’d like to help solve California’s problems with election district gerrymandering.  I’m currently applying to be a California Redistricting Commission as part of the Voters FIRST Act (Proposition 11).

My goal would be to remove as much subjectivity as possible from the redistricting process.  As a software engineer, I feel that a computer algorithm should be able to handle the redistricting process much better than any human being objectively could.  I’ve already been looking at multiple algorithms and have begun writing implementations.  As I analyze potential solutions, I’ll keep everyone posted via this blog.

Wish me luck!