WEIGHTED REGION PROBLEMS: THEORY AND ALGORITHMS

本研究关注加权区域问题的研究，并从理论和算法设计两方面探讨适合实现的算法。在加权区域框架中，平面或空间被划分为区域，每个区域都有一个相关的正权重。该框架可用于解决各种领域中出现的问题，包括规划对自然灾害的快速响应、军事应用（监视、可达性、路径规划）以及诸如生物医学计算等新兴领域。PI研究最优路径规划问题（k-链路最短路径，加权风险图背景下城市地区的疏散规划），最近邻问题，以及反向问题，其中目标是在相同采样查询的结果可用时找到未知权重。对于每个问题，寻求两个关键目标：(1)研究和发现基本属性，可以为竞争解决方案的定量，定性和比较评估提供基础；(2)开发解决问题的软件工具包，可以有效地用于实际应用。该研究的主要智力价值是为一些加权区域问题提供了一般和基本的方法。一般性质的结构被公式化。开发了高效的计算算法。对当前方法的重大限制放宽了。这项研究的广泛影响包括加强计算机科学与其他科学之间的联系。这项研究与科学、工程和政府的其他领域直接相关。PI设有一个网站，向公众公布和获取研究成果。

This research is concerned with the study of weighted region problems, and addresses both theory and design of algorithms suitable for implementation. In the weighted region framework the plane, or space, is partitioned into regions, each having associated a positive weight. This framework can be used for problems arising in various areas including planning rapid responses to natural disasters, military applications (surveillance, reachability, path planning), and newly emerging fields such as biomedical computing. The PI studies optimal path planning problems (k-link shortest paths, evacuation planning in urban areas in the context of weighted risk maps), nearest neighbor problems, and reverse problems in which the goal is to find unknown weights when the results to same sampling queries are available. For each problem, two key objectives are sought: (1) the study and discovery of fundamental properties, that can provide the basis for quantitative, qualitative and comparative evaluation of competing solutions and (2) the development of a software toolkit for solving the problem, which can be effectively used in practical applications. The leading intellectual merit of the research is to provide general and fundamental methods for a number of weighted region problems. Structures of a general nature are formulated. Efficient computing algorithms are developed. Significant restrictions on current approaches are relaxed. Broader impacts of this research include strengthening the interface between computer science and other sciences. The research has direct relevance to other areas of science, engineering and government. The PI maintains a web site on which research results are made known and available to the public at large.