CAREER: Theory and Practice of Applied Geometric Computing

Polytechnic University Of New York, Brooklyn NY

Investigators

Abstract

Computational geometry arose out of the need for many science and engineering applications of geometric computing. Over the last two decades, the field has emerged as a rich, mature, and mathematically rigorous discipline. However, despite its impressive achievements well-received in the theoretical computer science community, computational geometry has had limited impact in the practical areas of geometric computing. As advocated by the recent Computational Geometry Task Force Report, it is important to reorient the field towards providing more practical solutions to the specific needs of the applications that use geometric computing, and towards focusing on new "bottleneck" problems of identifiably important practical areas. In this proposed career plan, we intend to develop our research career toward this goal, by working on the full computational pipelines of some important real-world applications of geo-metric computing, including air traffic management (conflict prediction), graphics and scientific visualization (I/O-efficient isosurface extraction, I/O- efficient direct volume rendering, external-memory view- dependent surface simplification), and manufacturing (maximum scatter traveling salesperson problem (TSP)). An important aspect of the work is to examine the full computational pipelines of the practical applications to identify and formulate critical tasks into new algorithmic questions, extend computational geometry methodologies to devise novel solutions, and finally implement and integrate the developed algorithms into the pipelines to evaluate their practical ef-fectiveness in the original real-life applications. Key components of the plan are the expected rich interactions between theory and practice, and the aim of designing simple, easy-to-implement geometric algorithms that are efficient both practically and theoretically. In the long term, we expect to be able to have real impact on these important practical areas of geometric computing, and at the same time enrich the knowledge body of the field of computational geometry. The proposed educational plan includes introduction of new courses, involvement of both graduate and undergraduate students in the proposed research projects, participation in an outreach program, and further development of a research laboratory.