Geometric Computing

几何计算

• 批准号: RGPIN-2019-06646
• 负责人: Bose, Prosenjit
• 金额: $ 4.01万
• 依托单位: Carleton University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=715051
• 关键词: 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)如何构造具有某些理想性质的几何网络？ 在我的研究中，解决几何问题的一个统一主题是首先发现问题所涉及的结构的各种几何性质，然后尝试利用这些性质来设计有效的数据结构和算法来解决几何问题。