Gerrymandering on a high-genus surface/can I use my powers for evil?

Somewhat in contrast to this question.

Let’s say the Supreme Court has just issued a ruling that the upper and lower roads of an overpass need not be in the same congressional district. This makes states with lots of overpasses into high-genus surfaces for the purpose of gerrymandering. I, an unscrupulous mathematician, get a call from my state legislature, asking me to consult for them about how best to place new roads in order to achieve their desired district layout, in exchange for a generous fee.

Specifically, my state is a rectangle with no existing roads or overpasses. It has n congressional districts. The state legislature has in mind a collection {Pi,j} of convex polygons with nonempty interior which tile the state, where i ranges from 1 to n and j from 1 to at most m for each i, and wishes for each Pi,j,Pi,j to be in the same congressional district, thus must be connected by roads (smooth curves). Any time a road passes through a polygon of a different congressional district, an overpass must be built across it to avoid disrupting the other district. Any time two roads meet, an overpass must also be built. Note that for any fixed i, some but not all of the Pi,j may be empty. The legislature wants to know the minimum number O(n,m) of overpasses that need to be built in order to facilitate their gerrymandering, in the worst-case scenario.

Equivalently, take a tiling of the unit square S by convex polygons Pi,j, and n-color them such that at most m polygons have the same color. For each color i, choose smooth curves λi1,,λiri:[0,1]S such that
mj=1Pi,jrik=1im(γik) is connected. For each color i, choose points pi1,,pisi such that
(mj=1Pi,j(iirik=1im(γik))){pi1,,pisi}
is connected. If we can choose the curves and points freely, then O(n,m) is the worst-case (among all choices of tiling and coloring) minimum possible value of ni=1si.

Clearly O(n,1)=0. A very rough upper bound is O(n,m)n(m1)(nm1) since we can connect the necessary districts by drawing n(m1) curves, none of which touch the boundary and each of which intersects at most all nm1 other districts, and intersect each polygon in straight lines. A rough lower bound comes from dividing the square into nm vertical strips and coloring them cyclically, i.e. red, yellow, blue. red, yellow, blue etc. Then any path which connects all districts of the same color must pass through at least all but one district of each other color, so O(n,m)(n1)(m1).

Can these bounds be improved upon, or even an exact formula be found?

Note: For those of you not in the United States, this question won’t make much sense unless you’re familiar with gerrymandering.

Edit: This question was inspired by my state legislature (Kansas), which tried to make a congressional district which consisted of the conservative western third of the state, a road going across the state, and two liberal cities along the eastern border.

Edit 2: For the purposes of this problem, I assume that at most two roads meet at any overpass.

Answer

Can we not ignore multiplicities of overpasses, at least in the second formulation of the problem? We know that each polygon with a path through it requires at least one overpass. But if we have a polygon with any number of paths through it, such as:
enter image description here

Can we not replace these path segments with a piecewise linear path the goes from one boundary point, which remains the same, to some central overpass, to another boundary point. This would give the following:

enter image description here

Which doesn’t affect anything outside of the polygon and reduces all paths inside to one overpass. This gives an upper bound of mn.

Attribution
Source : Link , Question Author : Alex Becker , Answer Author : guest196883

Leave a Comment