Algorithms in computational geometry and geometric graphs

计算几何和几何图的算法

• 批准号: RGPIN-2020-03959
• 负责人: Lubiw, Anna
• 金额: $ 3.5万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=739591
• 关键词: 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形状的应用问题。一个著名的开放问题是，我们是否可以切割任何凸多面体的一些边，以在平面上给出一个不重叠的“网”。在实际应用中，我们可以横切面部，而众所周知，这种松弛存在网。然而，有些网比其他网更好——我建议找到有效的算法来解决最小化切口长度或包围网的最小圆盘大小的相关优化问题，这两者在应用中都是相关的。