Project 3: Gerrymander

Arcadia is a country whose land forms an exact square of side length 1 foobar. The population of voters in Arcadia is p. The country elects its government in a fairly standard way. Arcadia is divided by law into n districts. Each district has the following properties:

• It is contiguous, without articulation points.
• Its boundary is a set of connected line segments, each of which is parallel to one of the borders of Arcadia.
• The number of voters living in the district is within ten percent of p/n, the average voter population per district.

Further, every point in Arcadia is covered by exactly one district. Note the parallel boundary condition, which rules out some (but not all) ``odd'' shapes.

Arcadia has q political parties, all of whom nominate a candidate in each district. Voters in each district choose a single candidate, and the candidate with the most votes in the district is the winner. In the event of a tie, a coin is tossed to determine the winner from among those in the tie.

The votes of the most recent election are available on a voter by voter basis. (Arcadia has never been an advocate for privacy.) For each voter we have a record of

• The exact x and y coordinates where the voter lives.
• The party (from 1 to q) that the voter chose in the most recent election.

Note that more than one voter may live at the same location. Despite its regular boundaries, Arcadia is far from homogeneous in its population, and different parties have strength in different regions of the country.

In its wisdom, the framers of the Arcadian constituion require the chief electoral officer (namely, you) to certify after each election that the districts are not gerrymandered. As part of your reporting requirements, you are asked to determine the following for each party r in $\{1,\ldots,q\}$:

Given the voting pattern of the most recent election, what is the maximum number of districts that would have been won by party r if party r had been allowed to choose the district boundaries.

Recognizing that an exact solution to this problem might be computationally intractable (the authors of the constitution included a computer scientist), you are permitted to report a ``best estimate'' with justification. Upper and lower bounds on this number are also required. The hope is that by publishing these numbers, together with the actual results, voters will have confidence that the boundaries do not favor any particular party.

Your job is to write a computer program to determine these estimates.

Your program should read in a file containing the results of the most recent election, and output for each party the best estimate, lower bound, and upper bound numbers. The input file has the following format: The first line contains the total voter population p, the number of parties q, and the number of districts n. Subsequent lines contain (double precision) x and y coordinates and (integer) party preference information, one line per voter. All fields are separated by white space (spaces or tabs). The output should consist of q lines, with each line having the form

r e l u

where r is the party number, e is the best estimate, l is the lower bound, and u is the upper bound. Results should be generated in the order of r. For each lower bound you must also generate a set of boundaries that achieves the lower bound. Those boundaries must be written to q files (one per party) in a format that can be visualized using a standard tool (such as a browser or postscript viewer).

The voter preference distribution is likely to be important. Some sample distributions will be provided. Nevertheless, your programs will be expected to work for distributions you have not previously encountered. Your answers (particularly the lower bound) will be compared with those of other groups.