Given the generality and popularity of sweepline algorithms in computational geometry, I'm wondering where the problem is here. Can't you just move a sweepline across a given territory in any direction and get a result? If you want maximum outrage (largest value of X in smallest area), I agree that's more complex and I'm not sure how you would prove an optimum result.
It'd be curious what different countries look like in terms of gradient decent difficulty on population density. I'd imagine most look fairly similar (densely populated regional urban areas surrounded by rural), but I imagine there are exceptions to some degree out there?
This part is quite messy. For every given (c1,c2) city pair, you'd get 1 straight line that connects c1 to c2. Then for every city ck, you need info on whether ck is above that line or below - you can compute that by point-slope geometry with the lat-long coordinates ( given point p(x,y) & line l with some slope, is p above l or below ).
If you want to poke around, the dataset is here: http://seer.cancer.gov/popdata/
Given n (city,population, area) tuples for country C, find 2 cities, the line thru which slices C into two land masses M and N. M would then have k tuples and N would have n-k, such that the ratio of aggregate population of k tuples to the aggregate population of n-k would be 90+delta:10-delta, for delta in interval [1,9], whilst simultaneously you have the ratio of the aggregate area of the k tuples to the aggregate area of n-k working out to 1+nabla:1-nabla, for nabla in [0,0.5].
No idea what the optimal algorithm would be, short of brute force so O(n^2).
This is the sort of DS project a HuffPo would run - you can slice up countries not just based on 94:6 population but also crime rate, education, victims of homicide, what have you; all you need in tuples with larger arity.