WEIGHTED REGION PROBLEMS: THEORY AND ALGORITHMS

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

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.