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.