WEIGHTED REGION PROBLEMS: THEORY AND ALGORITHMS

University Of Texas At Dallas, Richardson TX

Investigators

Abstract

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.