Algorithms in computational geometry and geometric graphs

计算几何和几何图的算法

• 批准号: RGPIN-2020-03959
• 负责人: Lubiw, Anna
• 金额: $ 3.5万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750215
• 关键词: Algorithms; computational; geometry; geometric; graphs

My research is in design and analysis of algorithms, specifically for problems involving geometry and graphs. Currently, I focus on reconfiguration of geometric structures and graphs: How can one structure be changed to another, either through continuous motion or through discrete changes?  Examples in popular culture include Rubik's cubes and transformers; in mathematics, the topic has a vast and deep history, for example knot theory, and mechanical linkages. Reconfiguration can often be accomplished via discrete steps. The questions I propose answering are ones of: existence (can an initial structure be reconfigured to a target structure); distance (how many steps are needed for reconfiguration); and efficiency (is there an efficient algorithm to test existence or find the distance). These problems can be modelled as connectivity and shortest path problems in an exponentially large "reconfiguration graph'' where a vertex represents a configuration and an edge represents a reconfiguration step.  I propose to study the structure of such reconfiguration graphs, building on previous work with PhD students on reconfiguration of triangulations of a point set in the plane. Triangulations of a point set are heavily used in applications such as meshing, and the basic reconfiguration step, a "flip", is well-studied. In the process of studying flips in the edge-labelled setting, we discovered new topological properties of the reconfiguration complex, an enhancement of the reconfiguration graph. I will extend this to other settings, with the goal of furthering our understanding of the structure of reconfiguration graphs. "Morphing" is one kind of reconfiguration, and I will continue to work on problems of morphing graph drawings. Given two planar drawings of the same graph with points for vertices, and straight line segments for edges, the goal is to move continuously from the first drawing to the second, remaining planar throughout the motion. This problem has many applications in visualization and animation. We have developed a theoretically satisfactory algorithm to find a piece-wise-linear morph but many practical issues such as preventing vertices from coming too close to each other remain open. My work on reconfiguration in a more geometric setting focuses on unfolding polyhedra, a problem with applications in manufacturing 3D shapes out of metal, cardboard or plastic. One famous open question is whether we can cut some edges of any convex polyhedron to give a non-overlapping "net" in the plane. In practical applications we may cut across faces, and nets are known to exist for this relaxation. However, some nets are better than others - I propose to find efficient algorithms to solve associated optimization problems of minimizing the length of the cuts or the size of the minimum disc enclosing the net, both of which are relevant in applications.

我的研究方向是算法的设计和分析，特别是涉及几何和图形的问题。目前，我专注于几何结构和图形的重新配置：如何将一个结构改变为另一个结构，无论是通过连续运动还是通过离散变化？ 流行文化中的例子包括魔方和变形金刚;在数学中，这个主题有着广泛而深刻的历史，例如纽结理论和机械联系。重新配置通常可以通过离散步骤来完成。我建议回答的问题是：存在性（初始结构可以重新配置为目标结构）;距离（重新配置需要多少步骤）;和效率（是否有有效的算法来测试存在性或找到距离）。这些问题可以被建模为指数级大的“重新配置图”中的连通性和最短路径问题，其中顶点表示配置，边缘表示重新配置步骤。 我建议研究这种重构图的结构，建立在以前的工作与博士生在平面上的一个点集的三角剖分重构。点集的三角剖分在网格化等应用中得到了大量使用，并且基本的重新配置步骤“翻转”已得到充分研究。在研究翻转的过程中，在边标记设置，我们发现了新的拓扑性质的重新配置复杂，增强的重新配置图。我将把它扩展到其他设置，目的是加深我们对重新配置图的结构的理解。 “变形”是一种重构，我将继续研究变形图形绘制的问题。给定同一图形的两个平面图，顶点为点，边为直线段，目标是从第一个图形连续移动到第二个图形，在整个运动过程中保持平面。这个问题在可视化和动画中有许多应用。我们已经开发了一个理论上令人满意的算法来找到一个分段线性变形，但许多实际问题，如防止顶点太接近对方仍然开放。 我的工作在一个更几何设置的重新配置集中在展开多面体，一个问题的应用程序在制造3D形状的金属，纸板或塑料。一个著名的公开问题是，我们是否可以削减任何凸多面体的一些边缘，以提供一个不重叠的“网”在平面上。在实际应用中，我们可以切割面，并且已知存在用于这种松弛的网。然而，有些网是比别人更好-我建议找到有效的算法来解决相关的优化问题，最小化的切割长度或大小的最小圆盘包围网，这两者都是相关的应用程序。