But first a disclaimer: This is a really good and bad idea at the same time. It create a political minefield and possibly something controversial.
It's about the electoral map.
It all started back in November. There was talks in the media that the Quebec electoral map wasn't 100% correct. Some district were too populated and the map had to be re-drawn... The process was started but was too slow for it to be done for the upcoming election. It got me intrigued. I'm pretty sure the way the electoral map is drawn influence a lot the outcome of the election. But how? I wanted to find out.
I wasn't the first time this sort of questioning crossed my mind. Back in 2005, while I was still a student in my final year of Computer Engineering degree, I had a course on algorithms and graph theory. The kind of course were you learn that some problems are unsolvable, unless you have infinite time to solve them. I remember asking the teacher this very question: "Can't we use graphs to map were the votes are and tell if the electoral map is unjust?". He answered that it was possible, but no one would be willing to do this sort of stuff because it's too political.
And so, when the medias started talking about the electoral map, I remembered that talk I had with the teacher. I had an idea at the time of how one would analyze the various information sources to determine how well the electoral map is divided. Here's how I wanted to do it:
You make point of interests, containing all the votes in a giving sector. It could be a municipality of any other sort of subdivision. The more there is, the better. For example, in Quebec city, one could create a Point-of-interest at for voting spot, containing all the various boxes that were in that spot. Each spot has a weight based on the number of registered voters and is linked to the rest of the electoral district to form a single district. Once you have this map, you create "potential links", links from each P-O-I to various neighbors in other district (for example, the 3 closest neighbors not in the district). The create the various potential maps, you turn on and off each link until you have a legal, but different map.
OF course, there is a couple of problems with this approach.First, to do all this you need:
- Coordinates for each voting poll
- Number of voters for each voting poll
- Results for each poll
- District for each voting poll
Almost all this information is public, except for one: the exact location of each voting poll.The only information giving for each box is the municipality where the voting poll was. So all the maping information for the voting poll in Montreal, only says : "Location: Montreal". Hard to place the voting voting polls with so little information.
The second problem is the complexity of the entire process. My initial list had 1848 potentials P-O-I on the map. If you limits the links to the 5 closest neighbors, you still get somewhere between 3000 and 9000 links... Which means calculating between 2^3000 and 2^9000 possibilities... Which could take a very, very long time. (2^3000 is over 10^600, or 1 with 600 zeros)
After a couple of days of trying to find ways to optimize the algorithm, I simply gave up. There is not enough information to create a meaningful map, since the location information in large urban area is not very detailed and leads only to a partial answer...
It was a great idea, but I can't go further.
I guess my time is better spent elsewhere...
