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