Algorithms in computational geometry and geometric graphs

计算几何和几何图的算法

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