Optimization problems on geometric graphs

几何图的优化问题

• 批准号: 386206-2011
• 负责人: Vassilev, Tzvetalin
• 金额: $ 1.02万
• 依托单位: Nipissing University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=572926
• 关键词: Optimization; problems; 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.

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