Hi all,
I'm the one who made the map mentioned above (I saw a referral from this forum), so let me provide a justification for some of the decisions I've made:
1. Election results data is only available at the polling station level. In effect, I know where the polling stations are, but I do not know where the voters live, which is why the single member districts are based on the polling stations' coordinates.
2. Obviously, I can't split up polling stations (if I do that - how do I decide where each vote should go?). As such, districts are formed with just two operations:
- merge two adjacent districts
- move one polling station from district A to B, provided that the PS is adjacent to district B
3. This leads to the problem with the unequal district sizes. For example, there are polling stations in Sofia, Varna, etc. which have about 20000 voters each, and each and every one of their neighbours has also about 20000 voters. The ideal district size is about 30000, so as you can see - any district which has one of the weirdly large polling stations will be either much larger or much smaller that the desired size.
4. Separate polling stations on the same address (large schools) are treated as different, but neighbouring locations. This causes the narrow strips of single-polling-station districts near the centre of Sofia. This is largely an artefact of the visual representation and doesn't affect the numerical result.
5. Current multi-member district borders are respected mostly as a performance-oriented heuristic. Checking if two "new" districts are adjacent is slow - the total operations are (# of polling stations in district A) * (# of polling stations in district B). Checking if two "new" districts are in the same "old" district is a constant-time operation which, in practice, reduces the total time it takes to form the new district by more than four times.
Also, the standard deviation for the new district sizes is about 4800. The standard deviation without this heuristic is less than that, but again - more than 4000, mostly because of the large polling stations I mentioned above.
6. Further, removing this heuristic resulted in weird narrow, but long districts, some of which spanned the entire length of the country. With this heuristic in place, this problem is limited to a much smaller area. For example, locate the district which includes Sungurlare, Karnobat, Sredets and so on.
7. The non-contiguous districts are caused by the unfortunate fact that the country is not perfectly rectangular
Checking whether two districts are adjacent is already slow; checking whether their shared border is inside the country is slower. On the other hand, using a rectangle as a simplification of the shape of the country allows me to simply map the intersection of the country and the rectangle.
This is mostly a problem near the border, where the country is concave - see the north-western town of Vidin and the village of Novo Selo to its west (where either the entire Novo Selo should have been in Vidin's district or none of it), as well as the village of Rezovo near the border with Turkey which should have been in the district encompassing Primorsko, Tsarevo and Ahtopol, and not its current district of Malko Turnovo, Sredets and Karnobat.
-----
Finally, this is the algorithm:
- Split up the country in a number of districts, so that every district includes exactly one polling station.
- Quickly merge adjacent districts until there aren't any districts with less than 10000 voters.
- Reduce the number of districts to 240 by merging adjacent districts, but taking care to either decrease the standard deviation, or to only increase it by the smallest amount possible.
- Move polling stations from one district to another, provided that the standard deviation decreases with each move (repeat until stdev can't decrease any more).
