Optimization problems on geometric graphs

图形是计算机和通信网络、道路、水道以及任何 一般基础设施。自然会出现许多优化问题。例如，什么是最有效的 邮包通过互联网的路线，或两个地点之间的货件路线。效率本身可以是 以时间、成本、使用的中间节点数量等衡量。 CASES是图上的一个优化问题。我们研究图上的最优化问题。这样做的目的是 研究的目的是开发高效的算法技术和数据结构，以允许高效地解决 考虑过的问题。我们专注于几何图，即具有从 或与几何空间有关。这些是嵌入到度量空间中的图，即施加了度量的图 在它们的边上，或者其边具有某些几何性质的图。例如，相对的 一组点的邻域图(RNG)在无线路由、集群等方面有应用。 最常用和研究的几何图是三角剖分。它们被应用于地理 信息系统(包括GPS)、计算机图形和可视化、医学成像和 计算机引导的手术、网格划分和建模，仅举几例。每个应用程序都需要 具有一定性质和性质的三角剖分。同样重要的是，这些都是有效的可计算的， 特别是在对时间敏感的应用中。因此，我们快速有效地执行某些任务的能力依赖于 基于构造最优三角剖分的高效算法。最后，非常重要的是要研究 几何图的一般性质，以促进我们对计算的概念理解 范例。

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.