Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 $\{P_{i,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 $P_{i,j},P_{i',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 $P_{i,j}$ may be empty. The legislature wants to know the minimum number $\mathcal 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 $P_{i,j}$, and $n$-color them such that at most $m$ polygons have the same color. For each color $i$, choose smooth curves $\lambda_{i1},\ldots,\lambda_{ir_i}:[0,1]\to S$ such that $$\bigcup\limits_{j=1}^m P_{i,j}\cup \bigcup\limits_{k=1}^{r_i}\mathrm{im}(\gamma_{ik})$$ is connected. For each color $i$, choose points $p_{i1},\ldots,p_{is_i}$ such that $$\left(\bigcup\limits_{j=1}^m P_{i,j}\setminus \left(\bigcup\limits_{i'\neq i}\bigcup\limits_{k=1}^{r_{i'}}\mathrm{im}(\gamma_{i'k})\right)\right)\cup \{p_{i1},\ldots,p_{is_i}\}$$ is connected. If we can choose the curves and points freely, then $\mathcal O(n,m)$ is the worst-case (among all choices of tiling and coloring) minimum possible value of $\sum\limits_{i=1}^n s_i$.

Clearly $\mathcal O(n,1)=0$. A very rough upper bound is $\mathcal O(n,m)\leq n(m-1)(nm-1)$ since we can connect the necessary districts by drawing $n(m-1)$ curves, none of which touch the boundary and each of which intersects at most all $\leq nm-1$ 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 $\mathcal O(n,m)\geq (n-1)(m-1)$.

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.

share|improve this question
Redrawing boundary lines isn't specific to the U.S.! –  The Chaz 2.0 Jul 6 '12 at 23:46
@TheChaz Yes, but I wasn't sure the term gerrymandering was used elsewhere. –  Alex Becker Jul 6 '12 at 23:50
It sounds like the Kansas legislature should have simply glued their western and eastern borders. And changed their state nickname to the Cylinder State. :) –  Michael Joyce Jan 29 '13 at 23:50
add comment

1 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$.

share|improve this answer
I think there's an implicit assumption that at most two roads can meet at any overpass. Even in the real world, each overpass intersects at most a constant number of roads. –  JeffE Feb 5 '13 at 5:07
@JeffE I wholeheartedly agree with you. So this was more of a discussion of a fault in the problem statement than a true solution. –  Sam DeHority Feb 5 '13 at 5:11
Yes, I had implicitly assumed that at most two roads meet at any overpass. @JeffE Oh god, I've never seen anything so horrible! Actually, I can't recall ever seeing more than two roads meet at an overpass, but that's probably because Kansas doesn't have many. –  Alex Becker Feb 17 '13 at 21:48
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.