CAREER: Generalizing Planar Algorithms

计算拓扑是一个令人兴奋的新领域，出现在计算机科学和数学的交叉点。最简单的拓扑设置是平面（或二维欧几里得空间）。为平面对象开发快速算法对于许多应用至关重要，包括道路网络、集成电路设计和运动规划。将这些平面算法一般化，使它们能够在其他拓扑设置中快速运行，从而可以扩展到更大的应用领域，包括图形中的形状建模、医学成像、在统计分析中为高维数据寻找低维跨度、形状描述和检测、计算曲线或曲面之间的相似性度量，以及图形中的流和路由问题。PI将开发更快的算法来解决曲面图和小自由图中的基本问题，它们都是平面图的自然推广，提供额外的拓扑结构。更具体地说，PI将用于寻找曲面上最短的路径和循环，计算曲面上的最大流量和较小的自由流量，以及计算曲线之间的相似性度量等问题。除了设计更快的算法外，PI还将为这些算法中的一些实现实际设置的第一个代码，特别是在计算非平面上曲线之间的相似性度量方面。这项工作的大部分是在数学和计算机科学的交叉点，因此将导致PI的研究小组和这两个领域的其他研究人员之间的跨学科合作。协作和跨学科工作也为计算机科学教育和社区外展的进步提供了框架。PI活跃的跨学科研究小组将提供一个理想的论坛来指导本科生，特别是那些来自代表性不足群体的学生。本科生的研究反过来又会吸引有才华的学生进入计算机科学研究生院。此外，PI重新设计了几门计算机科学课程，以纳入一个大型的主动学习组件。PI将继续研究主动学习的教学方法及其对计算机科学专业学生招聘和留用的影响。

Computational topology is an exciting new area, emerging at the intersection of computer science and mathematics. The most simple topological setting is the plane (or two-dimensional Euclidean space). Developing fast algorithms for planar objects is vital for many applications, including road networks, integrated circuit design, and motion planning. Generalizing these planar algorithms so that they will run quickly in other topological settings allows one to extend to an even larger domain of applications, including shape modeling in graphics, medical imaging, finding low-dimensional spans for high-dimensional data in statistical analysis, shape description and detection, computing similarity measures between curves or surfaces, and flow and routing problems in graphs.The PI will develop faster algorithms for fundamental problems in graphs on surfaces and in minor free graphs, which are both natural generalizations of planar graphs that provide extra topological structure. More specifically, the PI will work on problems such as finding shortest paths and cycles on surfaces, computing maximum flows in surfaces and minor free flows, and computing similarity measures between curves. In addition to designing faster algorithms, the PI will also implement the first code for several of these algorithms for practical settings, particularly in the area of computing similarity measures between curves on non-planar surfaces. Much of this work is at the intersection of math and computer science, and so will lead to interdisciplinary collaboration between the PI's research group and other researchers in both areas.Collaboration and interdisciplinary work also provide the framework for advances in computer science education and community outreach. The PI's active interdisciplinary research group will provide an ideal forum to mentor undergraduate students, particularly those from underrepresented groups. Undergraduate research will in turn draw talented students to graduate school in computer science. In addition, the PI has redesigned several of the computer science courses to incorporate a large active learning component. The PI will continue this research on pedagogical methods for active learning and its effect on the recruitment and retention of students in computer science.