[math-fun] gerrymandering maths
Asimov: standard deviation of curvature of boundary.. limit for smooth curves approaching in "suitable sense". 0 for circle, infinite for Koch snowflake. WDS: Won't work. Consider the unit square. Approach it by using circular arcs of angle 90 degrees and radius r at the 4 corners, as r-->0+. Result: the integral of curvature^2 is 2*pi*r*(1/r)^2 = 2*pi/r --> infinity. A variant of Asimov's idea which has the advantage of not being *completely* silly, is to use the integral (along boundary) value of |curvature|. I frankly am dubious about any measure which employs derivatives -- as soon as you do that you are asking for trouble for any real world numerical purpose. And even worse (as in this case) second derivatives. But the quantity I just described can be defined somewhat without need of derivatives by taking advantage of the Gauss-Bonnet theorem. Specifically, the integral of curvature along any curve segment on which the curve is convex, equals the |difference| between final and initial angle of tangent ray, where be careful not to add the wrong multiple of 2*pi (angles being defined mod 2*pi). So as long as your curve is divisible into convex and convex-the-other-way segments, with all inflection points having a tangent line, then can compute this integral. Bad news: EVERY convex object has the SAME |curvature| integral, indicating this variant idea is still completely stupid. Baker: muttering about gas, boundaries made of rubber, minimize energy. Knight: other such mutterings. Soap bubbles got involved somewhere. WDS: actually, Baker's ideas are vaguely valid intuitions about the problem of dividing up a country into equipopulous districts while minimizing total cutlength; that is one of the 3 quality measured defined in my survey essay. The soap bubbles obey certain properties like 120-120-120 angles at junctions, each boundary is a circular arc with uniform (but different) gas pressures (population densities) on each side. Those would be theorems. However... unfortunately population densities in real world are NOT uniform, and anyhow the whole problem of optimizing the map with cutlength as quality measure, is (I proved) NP-hard. In fact I proved NP-hardness for exact optimal districting using all 3 of the quality measures recommended in my paper. As an OPEN PROBLEM: find, for one of the 3 main quality measures in my paper, a polytime districting algorithm you can prove produces a map within some constant factor of optimality (or prove no such algorithm exists if P != NP). I actually partly succeeded in this quest, in the sense I had a somewhat vague algorithm and a somewhat vague proof it approximated -- I never carried this through to completion, and this all is not discussed in my paper. The method I had in mind was very complicated, fairly high degree polynomial time, and involved some high powered computational-geometry algorithm-design ideas involving "dynamic programming" related to work by Joe Mitchell. If we assume my proof could have been made to work, the resulting algorithm and approx guarantee both would have been totally impractical.
participants (1)
-
Warren D Smith