Design, analysis and implementation of geometric and graph algorithms

几何和图形算法的设计、分析和实现

• 批准号: 195732-2011
• 负责人: Maheshwari, Anil
• 金额: $ 2.11万
• 依托单位: Carleton University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2012
• 资助国家: 加拿大
• 起止时间: 2012-01-01 至 2013-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=508271
• 关键词: Design; analysis; implementation; geometric; graph

We will design, analyze and implement algorithms for problems arising in computational geometry and graph algorithms. Wherever possible, we will show upper and lower bounds in terms of computing resources used (time, space, processors, I/Os), provide the proof of correctness, and show the optimality or approximation bounds. The problems that we will study will likely be an abstraction, or a simplification or a generalization of problems that occur in practice. In computational geometry, we will primarily focus on shortest path problems, spanners, constrained geometrical queries and data structures. In graph algorithms, the focus will be on planar separators, problems that are at the interface of geometry and graph theory, understanding graph theoretic properties of geometric spanners, designing algorithms for problems based on geometric graphs, and especially studying graph problems where the underlying problem domain is geometric. Over the next five years, we want to expand our existing work on geometric shortest path problems on polyhedral domains by designing algorithms for three-dimensional weighted shortest path problems, generalizing the weight requirements from fixed to continuous, finding a suitable triangulation which leads to the given shortest path distances, and finding practically-relevant algorithms. We will expand our research work on geometric spanners by designing spanners for constrained domains that satisfy useful graph-theoretic properties that will likely lead to faster algorithms. We will further expand our work on `localized geometric queries' (e.g., find the largest empty circle containing a query point). The speed-constrained versions of the Frechet distance (which is a very commonly used similarity measure between two curves) based problems and their variants will be further explored. Some of our algorithms and techniques may find applications in designing economical and efficient networks, finding short, time-optimum, paths in geographical domains, and ways to represent geometric data succinctly to answer queries efficiently.

我们将设计，分析和实现算法的计算几何和图形算法中出现的问题。只要有可能，我们将显示所使用的计算资源（时间、空间、处理器、I/O）的上界和下界，提供正确性证明，并显示最优性或近似界。我们将要研究的问题可能是对实践中出现的问题的抽象、简化或概括。在计算几何中，我们将主要集中在最短路径问题，空间，约束几何查询和数据结构。在图形算法中，重点将放在平面分离器，几何和图论接口的问题，理解几何空间的图论属性，基于几何图形设计问题的算法，特别是研究图形问题，其中底层问题域是几何的。 在接下来的五年里，我们要扩大我们现有的工作几何最短路径问题的多面体域设计算法的三维加权最短路径问题，推广的重量要求从固定到连续，找到一个合适的三角形，导致给定的最短路径距离，并找到实际相关的算法。我们将通过为满足有用的图论性质的约束域设计空间来扩展我们在几何空间上的研究工作，这些性质可能会导致更快的算法。 我们将进一步扩展我们在“局部几何查询”方面的工作（例如，找到包含查询点的最大空圆）。基于速度约束的Frechet距离（这是两条曲线之间非常常用的相似性度量）的问题及其变体将被进一步探讨。 我们的一些算法和技术可能会在设计经济高效的网络，找到短，时间最优，在地理域中的路径，并以简洁的方式表示几何数据，以有效地回答查询中找到应用。