CAREER: Generalizing Planar Algorithms

职业：推广平面算法

• 批准号: 1054779
• 负责人: Erin Chambers
• 金额: $ 40.12万
• 依托单位: Saint Louis University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-06-01 至 2017-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1054779&HistoricalAwards=false
• 关键词: CAREER; Generalizing; Planar; Algorithms

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.

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