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 形状的应用程序中的一个问题，一个著名的悬而未决的问题是我们是否可以切割任何凸多面体的一些边缘以给出不重叠的“网”。 “在平面中。在实际应用中，我们可能会切过面，并且众所周知，网络是为了这种松弛而存在的。然而，有些网络比其他网络更好——我建议找到有效的算法来解决相关的优化问题，即最小化面的长度削减或包围网的最小圆盘的尺寸，两者在应用中都相关。