GOALI: Region Partitioning

这项拨款资助了快速几何算法的发展，用于将给定区域划分为多个部分。这些算法将被开发用于寻求划分区域的各种情况，例如重新划分，绘制器官移植区域（首先在同一区域内寻找器官匹配），绘制空中交通管制区域（或动态调整它们），以及将区域划分为一组车辆，以便更好地监视/调查该区域或为分布在该区域的客户提供服务。在这些应用中，算法将寻求满足和/或优化不同的标准。重新划分选区的标准是每个地区包含相同的人口，并优化竞争或紧凑性等目标。另一方面，器官移植区域的划分应该包含一个移植中心，并优化效率（很少有器官被浪费）和公平（不同地区的人接受器官的机会大致相同）的组合。在空中交通管制方面，我们力求平衡和减少空中交通管制区域的工作量。车辆路线问题的目标是使完成对区域的调查或为所有客户提供服务的时间最短。该基金还资助了已开发算法在理论和实践方面的性能分析（例如，为车辆问题开发的算法不会是最优的，因为这些问题是旅行推销员问题的推广，因此是NP困难的）。如果成功，这项研究将导致更公平、更紧凑的立法和国会选区；更有效和公平的器官移植地区；更有效率和负载均衡的空中交通管制区；以及物流和车辆路线的改进。它还将优化的范围从代数和组合问题扩展到几何问题。此外，它将提供一个框架和推广一些现有的问题在计算几何。

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.