This grant funds the development of fast geometric algorithms for dividing a given region into pieces. These algorithms will be developed for a variety of situations where one seeks to partition a region, such as redistricting, drawing organ transplant regions (matches for an organ are first sought within the same region), drawing air traffic control regions (or dynamically adjusting them), and dividing a region among a set of vehicles in order to better surveil/survey the region or serve customers distributed in the region. In each of these applications, the algorithms will seek to satisfy and/or optimize different criteria. Redistricting has the criteria that each district contains the same population and optimizes goals such as competitiveness or compactness. On the other hand, the organ transplant regions should be drawn so that each contains a transplant center and optimizes a combination of efficiency (few organs go to waste) and fairness (people in different regions have roughly equal chances of receiving an organ). In air traffic control we seek to balance and minimize the work load of the air traffic control regions. The goal in the vehicle routing problems is to minimize the time until the region is completely surveyed or all the customers have been served. This grant also funds performance analyses of the developed algorithms in both theory and practice (the algorithms developed for the vehicle problems, for example, will not be optimal since these problems are generalizations of the traveling salesman problem and are thus NP hard).
If successful, this research will lead to fairer, more compact legislative and congressional districts; more efficient and fair organ transplant regions; more efficient and load-balanced air traffic control regions; and improvements in logistics and vehicle routing. It will also extend the reach of optimization from algebraic and combinatorial problems to geometric ones. In addition, it will provide a framework and generalize a number of existing problems in computational geometry.
