[dxbydt]

This is such an interesting idea! Lots of potential.

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.

[theoh]

"tuples with larger arity" is just computer scientist speak for "take more things into account".

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.

[ethbro]

Given the city-local nature of most population density, I'd imagine a grow-out-from-cities + line fit model would work fairly well at lower computational complexity.

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?

[Retric]

There are not that many city's in any given country so N^2 is probably not a big deal. However, you can get approximate results by drawing a line at every angle through a country and then moving that line up and down. Then just look for city's near any good candidate lines.

[dxbydt]

> drawing a line at every angle through a country and then moving that line up and down.

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/