Design and Analysis of Algorithms for Problems in Computational Geometry

计算几何问题的算法设计与分析

• 批准号: RGPIN-2016-06229
• 负责人: Maheshwari, Anil
• 金额: $ 2.77万
• 依托单位: Carleton University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=687083
• 关键词: Design; Analysis; Algorithms; Problems; Computational

I study geometric problems within the framework of the design and analysis of algorithms. My long-term research objectives are to design, analyze and implement algorithms for problems that require spatial information and (a) are fundamental, (b) have practical significance, (c) are theoretically challenging and have the potential to raise new questions, (d) contribute to an understanding of a methodology or concept, and (e) lead to the development of generic techniques and tools that can be applied to other problems. This requires developing efficient algorithmic solutions, establishing combinatorial and geometric properties, designing appropriate data structures, providing correctness proofs and complexity bounds, and possibly implementations. In the short term, my research focus is in three interrelated areas: geometric graphs, geometric location analysis and geometric path problems. My work in geometric graphs is centred around establishing graph theoretic and geometric properties of the underlying spatial configuration that can lead to efficient algorithmic solutions. In geometric location analysis, we design algorithms to determine an optimal location for facilities. I plan to continue my research work on weighted shortest paths by exploring variants and applications in two and three-dimensional settings.***As an illustration of my research directions consider the unit-disk graphs (UDG). UDG is a well-known class of geometric graphs that is often used to model the topology of ad hoc wireless communication networks. Each node, modelling an omni-directional antennae in the network, is viewed as a point in a plane. There is an edge between two nodes if the corresponding points are within a unit distance (signal strength outside this range is considered feeble). A signal can travel from one node to another if there are intermediate nodes between them so that a signal can hop from one node to other, each within a unit distance of its predecessor until it reaches the destination node. To check the connectivity between any pair of nodes, we can use a graph connectivity algorithm, and the time required is proportional to the size of the graph. Depending on the spatial configuration of the input nodes, a UDG can be anywhere from being very sparse to very dense. Therefore, the runtime of the configurations corresponding to the dense graphs is significantly higher than those corresponding to sparse graphs. By exploiting the geometric properties, we can design an algorithm to test the connectivity of UDG and ensure that its run-time is independent of the number of edges. Fundamental questions such as how to efficiently find a shortest hop path between a pair of query nodes, how to efficiently determine the diameter, and how to efficiently determine various graph parameters related to coverage, connectivity and interference questions in UDGs and the associated wireless networks remain unresolved. *** **

我在算法设计和分析的框架内研究几何问题。 我的长期研究目标是设计，分析和实现算法的问题，需要空间信息和（a）是基本的，（B）有实际意义，（c）在理论上具有挑战性，并有可能提出新的问题，（d）有助于理解的方法或概念，以及（e）导致开发可应用于其他问题的通用技术和工具。这需要开发有效的算法解决方案，建立组合和几何属性，设计适当的数据结构，提供正确性证明和复杂性界限，并可能实现。在短期内，我的研究重点是三个相互关联的领域：几何图，几何位置分析和几何路径问题。我的工作在几何图形是围绕建立图形理论和几何属性的基础空间配置，可以导致有效的算法解决方案。在几何位置分析中，我们设计算法来确定设施的最佳位置。我计划通过探索二维和三维环境中的变体和应用，继续我对加权最短路径的研究工作。作为我的研究方向的说明考虑单位圆盘图（UDG）。 UDG是一个著名的几何图形，通常用于建模的ad hoc无线通信网络的拓扑结构。每个节点，模拟一个全向天线在网络中，被视为一个点在一个平面上。如果两个节点之间的对应点在单位距离内，则在两个节点之间存在边缘（此范围之外的信号强度被认为是微弱的）。信号可以从一个节点传播到另一个节点，如果在它们之间存在中间节点，使得信号可以从一个节点跳到另一个节点，每个节点在其前任的单位距离内，直到它到达目的地节点。要检查任何一对节点之间的连通性，我们可以使用图连通性算法，所需的时间与图的大小成正比。根据输入节点的空间配置，UDG可以是从非常稀疏到非常密集的任何地方。因此，对应于密集图的配置的运行时间显著高于对应于稀疏图的配置。通过利用UDG的几何性质，我们可以设计一个算法来测试UDG的连通性，并确保其运行时间与边的数量无关。诸如如何有效地找到一对查询节点之间的最短跳路径、如何有效地确定直径以及如何有效地确定与UDG和相关联的无线网络中的覆盖、连接和干扰问题相关的各种图形参数等基本问题仍然没有解决。*** **