CAREER: Theory and Practice of Applied Geometric Computing

计算几何起源于几何计算的许多科学和工程应用的需要。在过去的二十年里，该领域已经成为一门丰富、成熟和数学严谨的学科。然而，尽管其令人印象深刻的成就在理论计算机科学界广受好评，但计算几何在几何计算的实际领域中的影响有限。正如计算几何工作队最近的报告所倡导的那样，重要的是重新确定该领域的方向，以便为使用几何计算的应用的特定需求提供更实用的解决方案，并侧重于可确定的重要实践领域的新的“瓶颈”问题。在这个拟议的职业生涯规划中，我们打算通过致力于地理测量计算的一些重要现实应用的全计算管道来朝着这一目标发展我们的研究生涯，这些应用包括空中交通管理(冲突预测)、图形和科学可视化(I/O高效等值面提取、I/O高效直接体绘制、基于外部存储器的视点相关的曲面简化)和制造(最大散布旅行推销员问题(TSP))。这项工作的一个重要方面是检查实际应用的全部计算流水线，以识别关键任务并将其表述为新的算法问题，扩展计算几何方法以设计新的解决方案，最后将所开发的算法实现并集成到流水线中，以评估它们在最初的现实应用中的实际有效性。该计划的关键组成部分是理论和实践之间预期的密切互动，以及设计简单、易于实现的几何算法的目标，这些算法在实践和理论上都是有效的。从长远来看，我们希望能够对几何计算的这些重要实用领域产生真正的影响，同时丰富计算几何领域的知识体系。拟议的教育计划包括引入新课程，让研究生和本科生参与拟议的研究项目，参与推广计划，以及进一步发展研究实验室。

Computational geometry arose out of the need for manyscience 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 thetheoretical computer science community, computationalgeometry has had limited impact in the practical areas ofgeometric computing. As advocated by the recentComputational Geometry Task Force Report, it is important toreorient the field towards providing more practicalsolutions to the specific needs of the applications that usegeometric computing, and towards focusing on new"bottleneck" problems of identifiably important practicalareas. In this proposed career plan, we intend to developour research career toward this goal, by working on the fullcomputational pipelines of some important real-worldapplications of geo-metric computing, including air trafficmanagement (conflict prediction), graphics and scientificvisualization (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)). Animportant aspect of the work is to examine the fullcomputational pipelines of the practical applications toidentify and formulate critical tasks into new algorithmicquestions, extend computational geometry methodologies todevise novel solutions, and finally implement and integratethe developed algorithms into the pipelines to evaluatetheir practical ef-fectiveness in the original real-lifeapplications. Key components of the plan are the expectedrich interactions between theory and practice, and the aimof designing simple, easy-to-implement geometric algorithmsthat are efficient both practically and theoretically. Inthe long term, we expect to be able to have real impact onthese important practical areas of geometric computing, andat the same time enrich the knowledge body of the field ofcomputational geometry. The proposed educational planincludes introduction of new courses, involvement of bothgraduate and undergraduate students in the proposed researchprojects, participation in an outreach program, and furtherdevelopment of a research laboratory.