Optimal political districting: an interactive computer graphics system

An interactive computer graphics system is developed for application to the solution of political districting problems. The foundation for the system is a previously developed two phase algorithm which finds all optimal solutions, for a given set of criteria, to the districting problem. The first phase generates all feasible districts while the second phase selects the optimal plan. The optimal solution is the set of districts covering the entire area and minimizing the maximum deviation of any district population from the mean district population. The interactive graphics system allows input of map points for any area, determination of the optimal districting plan for an area, and graphic display of the map and optimal solution. Additionally, during execution of the graphics routine, specific boundaries may be interactively selected as either necessary or inappropriate to exist in a solution. The system determines the new optimal plan based on the additional criteria specified during the interactive graphics routine, and displays the new map and optimal solution. Computational and graphical results are given for real problems. Additionally, enhancements to the system are considered.