Geometric Computing

几何计算

• 批准号: RGPIN-2019-06646
• 负责人: Bose, Prosenjit
• 金额: $ 4.01万
• 依托单位: Carleton University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=739026
• 关键词: Geometric; Computing

My research area is Computational Geometry, a field devoted to the design and analysis of algorithms and data structures for geometric problems. My research focuses both on theoretical and practical issues. The geometric application areas I concentrate on include online routing and path planning in networks, building geometric spanners with various properties, drawing and visualizing graphs, and optimizing various geometric structures. An algorithm that is proven to be theoretically efficient often fails to be practically useful as it may only become efficient when the size of the problem is unreasonably large or the algorithm may be too complex to implement. However, the existence of theoretically efficient algorithms often provides insights into a problem and leads to the development of algorithms that are equally efficient in practice. The main goal of my research has been and continues to be to bridge the gap between theoretical and practical efficiency by finding practical algorithmic solutions to applied geometric problems that have theoretical performance guarantees. Below, I provide an example of the type of geometric problems I am currently concentrating on. More detailed and complete descriptions are provided in the proposal. Communication networks often have an inherent geometric component since the communication devices have physical locations. These networks are often modeled by geometric graphs. A geometric graph is a graph where each vertex is a point in the plane (or possibly higher dimensions depending on the application) and an edge is a line segment or a curve joining two points. The edges are often weighted to represent the distance between two points (or the communication cost etc.). A fundamental problem in this area is to find a path (usually as short as possible) between two points in the graph. Currently, I am applying my expertise in geometry to develop algorithms that take advantage of the geometric component of these graphs to find short paths in an efficient manner. The problems in this area are particularly challenging since the network is often dynamic, i.e. the devices may be moving and edges may appear or disappear. Moreover, this dynamic nature means that no single entity has complete knowledge of the current state of the whole network, requiring the development of algorithms that are online, local and use little memory. This amounts to trying to find a path in a graph while the graph is changing. My research in this area focuses on the following themes: (1) How to route (i.e. find a path) efficiently in a geometric network in various settings, (2) how to construct geometric networks with certain desirable properties? A unifying theme in my research when solving a geometric problem has been to first uncover various geometric properties of the structures involved in the problem, then to attempt to exploit these properties to design efficient data structures and algorithms to solve the geometric problem.

我的研究领域是计算几何，致力于几何问题的算法和数据结构的设计和分析领域。我的研究集中在理论和实践问题。我专注于几何应用领域包括网络中的在线路由和路径规划，构建具有各种属性的几何空间，绘制和可视化图形，以及优化各种几何结构。一个被证明是理论上有效的算法往往无法在实际中使用，因为它可能只会成为有效的问题的大小是不合理的大或算法可能太复杂，无法实现。然而，理论上有效的算法的存在往往提供了对问题的见解，并导致在实践中同样有效的算法的发展。我的研究的主要目标一直是，并将继续是弥合理论和实际效率之间的差距差距，找到实用的算法解决方案，应用几何问题，有理论性能保证。下面，我提供了一个我目前专注于的几何问题类型的例子。在提案中提供了更详细和完整的描述。通信网络通常具有固有的几何组件，因为通信设备具有物理位置。这些网络通常由几何图建模。几何图形是这样的图形，其中每个顶点是平面中的一个点（或者可能是更高的维度，取决于应用），并且边是连接两个点的线段或曲线。边缘通常被加权以表示两点之间的距离（或通信成本等）。这一领域的一个基本问题是找到图中两点之间的路径（通常尽可能短）。目前，我正在运用我在几何方面的专业知识开发算法，利用这些图的几何组成部分，以有效的方式找到短路径。这一领域的问题特别具有挑战性，因为网络通常是动态的，即设备可能会移动，边缘可能会出现或消失。此外，这种动态性意味着没有一个实体完全了解整个网络的当前状态，这就需要开发在线、本地和使用很少内存的算法。这相当于试图在图形发生变化时在图形中找到路径。我在这一领域的研究主要集中在以下几个方面：（1）如何在各种环境下有效地在几何网络中路由（即找到路径），（2）如何构造具有某些期望属性的几何网络？在我的研究中，解决几何问题的一个统一主题是首先发现问题中所涉及的结构的各种几何属性，然后试图利用这些属性来设计有效的数据结构和算法来解决几何问题。