CAREER: Theory and Practice of Applied Geometric Computing

职业：应用几何计算的理论与实践

• 批准号: 0093373
• 负责人: Yi-Jen Chiang
• 金额: --
• 依托单位: Polytechnic University of New York
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-09-01 至 2009-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0093373&HistoricalAwards=false
• 关键词: CAREER; Theory; Practice; Applied; Geometric

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.

计算几何是几何计算在许多科学和工程应用中的需要而产生的。在过去的二十年里，该领域已经成为一个丰富、成熟和数学上严格的学科。然而，尽管它令人印象深刻的成就深受理论计算机科学界，计算几何在几何计算的实际领域的影响有限。正如最近的计算几何工作组报告所倡导的那样，重要的是重新定位该领域，为使用几何计算的应用程序的特定需求提供更实用的解决方案，并专注于可识别的重要实用领域的新“瓶颈”问题。在这份职业规划中，我们打算通过研究地理测量计算的一些重要现实应用（包括空中交通管理）的完整计算管道，来实现这一目标（冲突预测），图形和科学可视化（I/O高效等值面提取、I/O高效直接体绘制、外部存储器视图相关表面简化），最大离散旅行商问题（Maximum Scatter Traveling Salesman Problem，TSP）工作的一个重要方面是检查实际应用的完整计算流水线，以识别和制定关键任务到新的算法问题，扩展计算几何方法来设计新的解决方案，并最终实现和集成开发的算法到流水线中，以评估其在原始现实生活应用中的实际效率。该计划的关键组成部分是理论与实践之间的预期互动，以及设计简单，易于实现的几何算法，在实践和理论上都是有效的。从长远来看，我们期望能够对几何计算的这些重要的实际领域产生真实的影响，同时丰富计算几何领域的知识体系.拟议的教育计划包括引进新课程，研究生和本科生参与拟议的研究项目，参与推广计划，并进一步发展研究实验室。