Algorithms in computational geometry and geometric graphs

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

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.