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?