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.