AF: Small: Collaborative Research: Efficient Algorithms for Cycles on Surfaces

AF：小型：协作研究：表面循环的高效算法

• 批准号: 1617951
• 负责人: Glencora Borradaile
• 金额: $ 34万
• 依托单位: Oregon State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-08-01 至 2021-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1617951&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; Efficient

Many computational problems start with a model that is a mesh or graph drawn on a surface. A classic example is the representation of a physical object for use in computer graphics systems by selecting points on the surface of the object and approximating the surface with triangles whose corners are the selected points: the points become the nodes and the sides of the triangles become the edges of a graph and the graph can be viewed as drawn on the surface of the object. When the surface is simpler, algorithms for manipulating a graph on the surface are more efficient; a surface is more complicated when it has features such as handles and holes. A common way to deal with these features is to simplify the surface by cutting the surface open to remove the handles and holes. This project will develop accurate and efficient methods for simplifying surfaces in this way as well as for other closely related problems. Because the problems are fundamental, new algorithms for them will provide efficient pre-processing tools for a wide range of applications. The PIs will involve graduate students in the research and, building on earlier successes and the fostering of a welcoming research environment, endeavor to recruit students from underrepresented populations.This project will address the above-described "cut-graph" problem as well as the problem of finding the minimum cycle-basis (a minimum-cost way to represent all the cycles in a graph) and the minimum homology-basis (a minimum-cost way to represent all the handles and holes in the surface on which the graph is drawn). For graphs on surfaces, these problems are very closely related. By considering these problems together, the PIs will develop fundamental techniques that will be translatable to other problems in these types of graphs. Cycle bases behave significantly differently in graphs on trivial (handle-free) surfaces than in non-trivial surfaces. For this reason, by further understanding the properties of surface graphs through the study of these problems, the PIs will provide the next step for algorithm design in surface graphs.

许多计算问题都是从一个模型开始的，这个模型是在一个表面上绘制的网格或图形。 一个经典的例子是在计算机图形系统中使用的物理对象的表示，通过选择对象表面上的点并用三角形近似该表面，三角形的角是所选择的点：点成为节点，三角形的边成为图形的边，并且图形可以被视为绘制在对象的表面上。 当表面更简单时，在表面上操作图形的算法更有效;当表面具有手柄和孔等特征时，表面会更复杂。 处理这些特征的常用方法是通过切开曲面以移除控制柄和孔来简化曲面。 这个项目将开发精确和有效的方法，以简化表面，以及其他密切相关的问题。 由于这些问题是基础性的，针对它们的新算法将为广泛的应用提供有效的预处理工具。 PI将让研究生参与研究，并在早期成功的基础上，培养一个友好的研究环境，本计画将解决上述的“割图”问题，以及寻找最小循环基的问题（表示图中所有循环的最小成本方式）和最小同源基（表示绘制图的表面中所有手柄和孔的最小成本方式）。 对于曲面上的图，这些问题是非常密切相关的。 通过将这些问题放在一起考虑，PI将开发出可转化为这些类型的图中的其他问题的基本技术。 圈基的行为显着不同的图平凡（无）表面比非平凡表面。 因此，通过对这些问题的研究，进一步理解曲面图的性质，PI将为曲面图的算法设计提供下一步。