Algorithms in computational geometry and graph drawing

计算几何和绘图中的算法

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

My research is in design and analysis of algorithms -- specifically in the areas of computational geometry and graph algorithms. ******Graph representations are ubiquitous in computer science, engineering and the sciences -- a few examples are: road/electical/internet networks in engineering, molecular structures in chemistry, and evolutionary trees in biology. Geometry, sometimes intrinsic, and sometimes imposed, is often a valuable part of a graph representation. A big part of my work is about devising algorithms to find, manipulate and utilize such geometric representations of graphs. Specifically, one of the topics I propose working on is algorithms to represent two graphs that share some vertices and edges, with the constraint that the shared part be represented consistently. ******A current active research area is the study of algorithms to "reconfigure" geometric or combinatorial structures. "Morphing" is a popular term for some special cases of reconfiguration. I propose working on algorithms to morph between two representations of the same graph while preserving some geometric structure such as planarity. I also propose working on reconfiguration of triangulations via discrete moves called "flips". ******In a more geometric vein, my work on reconfiguration focuses on folding and flattening polyhedra. These problems have applications in manufacturing 3D shapes out of metal, cardboard or plastic. One problem is to flatten the surface of a polyhedron (e.g. imagine flattening a paper bag) continuously without using too many creases. When the surface is not flexible, Cauchy's rigidity theorem limits what can be done; we are investigating how much of the surface must be cut or made flexible to permit flattening.**

我的研究是在算法的设计和分析方面 - 特别是在计算几何和图形算法领域。 ******图表在计算机科学，工程和科学中无处不在 - 一些例子是：工程学中的道路/选举/互联网网络，化学的分子结构以及生物学中的进化树。 几何形状，有时是固有的，有时是施加的，通常是图表表示的宝贵部分。 我的很大一部分是关于设计算法以查找，操纵和利用图形的几何表示。 具体来说，我建议的主题之一是表示两个共享某些顶点和边缘的图表，并限制了共享零件始终如一地表示。 ******目前的主动研究领域是对“重新配置”几何或组合结构的算法的研究。对于某些重新配置的特殊情况，“变形”是一个流行的术语。我建议在算法上工作以在同一图的两个表示之间变形，同时保留某些几何结构（例如平面性）。 我还建议通过称为“翻转”的离散动作来重新配置三角剖分。 ******在更加几何的静脉中，我在重新配置方面的工作集中在折叠和扁平化polyhedra上。 这些问题在用金属，纸板或塑料的制造3D形状中应用。 一个问题是在不使用太多折痕的情况下，不断地将多面体的表面（例如，想象一下纸袋变平）。 当表面不灵活时，凯奇的刚性定理会限制可以做什么。我们正在研究必须切割多少表面或使弹性柔韧以弄平。**