Optimization problems on geometric graphs

点击翻译按钮获取中文摘要

Graphs are the most general model for computer and communication networks, roads, waterways, and any general infrastructure. Naturally many optimization problems arise. For example, what is the most efficient route for a packet through the Internet, or for a shipment between two locations. The efficiency itself can be measured in terms of time, cost, number of intermediary nodes used, etc. The underlying problem in all such cases is an optimization problem on graphs. We study optimization problems on graphs. The goal of this research is to develop efficient algorithmic techniques, and data structures that allow efficient solutions for the problems considered. We concentrate on geometric graphs, i.e. graphs that have certain structure derived from or related to the geometric spaces. These are graphs embedded in metric spaces, graphs with a metric imposed on their edges, or graphs whose edges have certain geometric properties. For example, the Relative Neighbourhood Graph (RNG) of a set of points has applications to wireless routing, clustering, etc. One of the most commonly used and studied geometric graphs are the triangulations. They are applied to geographic information systems (including GPS), computer graphics and visualization, medical imaging and computer-guided surgery, meshing and modeling, just to mention a few. Every application requires triangulations with certain quality and properties. It is also very important that these are efficiently computable, especially in time-sensitive applications. Thus, our ability to perform certain tasks quickly and efficiently relies upon efficient algorithms for constructing optimal triangulations. Finally, it is very important to study the general properties of geometric graphs in order to advance our conceptual understanding of the computational paradigms.