Problems in Discrete and Computational Geometry

离散和计算几何问题

• 批准号: RGPIN-2020-04329
• 负责人: Biniaz, Ahmad
• 金额: $ 2.48万
• 依托单位: University of Windsor
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=739893
• 关键词: Problems; Discrete; Computational; Geometry

My research area is discrete and computational geometry. In discrete geometry we investigate properties of geometric objects with the objective of using these properties to design efficient algorithms in the field of computational geometry. Computational geometry is a branch of computer science devoted to the study of algorithms and data structures for geometric problems. The input of a computational geometry problem consists of geometric objects (such as points, lines, circles, etc.) that come from application domains such as wireless networks, computer graphics, and robotics. An algorithm that is proven to be theoretically efficient often fails to be practically useful as it may be too complex to understand and implement or it may only become efficient when the size of the input is unreasonably large. The main goal of my ongoing research is to seek a greater understanding of different geometric structures to design simple algorithms for geometric problems. I provide a sample of the type of problems that I will concentrate on. Technology used in daily life strongly relies on networks. For instance, one can think of the network of cellphone antennas in Canada. Since antennas have physical locations, this network can be modeled as a geometric graph where antennas are represented by points with connections/edges between any two antennas within each other's transmission range. Designing networks possessing various properties has a rich background. A required property for the cellphone network is that any two antennas should be able to exchange messages, and thus the network must be connected. This introduces the problem of computing a shortest connected network. Another problem is to replace omnidirectional antennas in wireless networks with directional antennas while maintaining network connectivity. Directional antennas are desirable in many ways, for example, they require lower transmission power and cause less interference. I will study these types of problems on geometric networks. Many structures studied in discrete and computational geometry have a requirement of being non-crossing, i.e., their edges do not cross each other. This is particularly true for sub-structures of complete geometric graphs that involve a minimization criteria, for example, the shortest connected network and shortest connected path. However, when the underlying graph is not complete or when we deal with a maximization criteria the non-crossing property is not guaranteed. Crossings can cause errors, for example, interference between antennas, collision between moving objects, or inconsistencies in the layout of a VLSI circuit. I will focus on computing non-crossing structures in these circumstances. A main framework that I exploit to solve geometric problems is to first extract various geometric and combinatorial properties involved in the input, and then combine these properties with suitable data structures to design efficient algorithms/solutions for the problem.

我的研究领域是离散和计算几何。在离散几何中，我们研究几何对象的性质，目的是利用这些性质来设计计算几何领域中的有效算法。计算几何是计算机科学的一个分支，致力于研究几何问题的算法和数据结构。计算几何问题的输入由几何对象(如点、线、圆等)组成。它们来自无线网络、计算机图形和机器人等应用领域。一种被证明在理论上是有效的算法往往没有实际用处，因为它可能太复杂，难以理解和实现，或者它可能只有在输入的大小不合理地大时才变得有效。我正在进行的研究的主要目标是寻求对不同几何结构的更多了解，以设计出几何问题的简单算法。我提供了一个我将专注于的问题类型的样本。日常生活中使用的技术强烈依赖于网络。例如，人们可以想到加拿大的手机天线网络。由于天线具有物理位置，因此可以将该网络建模为几何图，其中天线由在彼此传输范围内的任意两个天线之间具有连接/边的点来表示。设计具有各种性质的网络有着丰富的背景。手机网络的一个必要属性是，任何两个天线都应该能够交换消息，因此网络必须连接。这就引入了计算最短连通网络的问题。另一个问题是在保持网络连通性的同时，用定向天线取代无线网络中的全向天线。定向天线在很多方面都是可取的，例如，它们需要更低的发射功率和更少的干扰。我将研究几何网络上的这类问题。在离散几何和计算几何中研究的许多结构都要求不相交，即它们的边不相互交叉。对于包含最小化标准的完全几何图的子结构来说尤其如此，例如，最短连通网络和最短连通路径。然而，当底层图不完整时，或者当我们处理最大化准则时，不能保证不交叉性。交叉可能会导致错误，例如天线之间的干扰、移动对象之间的碰撞或VLSI电路布局中的不一致。我将专注于在这些情况下计算非交叉结构。我用来解决几何问题的一个主要框架是首先提取输入中涉及的各种几何和组合属性，然后将这些属性与合适的数据结构结合起来，为问题设计有效的算法/解决方案。