Fun map segmentations
Given a convex polygon and a set of points, our original algorithm partitions the polygon into convex pieces of equal area so that each piece contains one point. We can extend this in a number of ways, equitably partitioning arbitrary densities, as shown below.
We can partition the USA into 48 states, each having the same number of republicans and democrats, with each state having equal population. The result is actually not hugely surprising -- you get a lot of long, thin states, intersecting the traditionally right-leaning heartland and the traditionally left-leaning east coast.
Here we take the convex hull of the continental USA as our polygon
and the 48 state capitals as our points. Thus, each state has convex land borders, and has the same capitals as before, but now they all have equal area. Notice that Illinois now
has a Pacific coastline. I've tried to make an example where a state
has both oceans in its boundary, but no such luck yet.
These are the most common examples that people draw when they're dubious of the claim that an equitable partition always exists:
Here's a partition that's not taken with respect to area, but to the total length of roads in a sub-region:
