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电路布局的不一致。我将集中在计算非交叉结构在这些情况下。我用来解决几何问题的一个主要框架是首先提取输入中涉及的各种几何和组合属性，然后将这些属性与合适的数据结构联合收割机结合起来，为问题设计有效的算法/解决方案。