CAREER: Fundamental Geometric Algorithms

物理世界和抽象信息的几何表示渗透到科学和工程中。几何对象上的算法是数学编程、计算机图形学、机器人、数据挖掘、信息检索、计算结构生物学、科学计算和机器学习的核心。这项研究跨越了几何算法设计的当前议程，并解决了其解决方案可能影响上述领域的基本问题。研究追求四个关键主题：线性规划和计算机科学中相关多面体理论问题的新算法的设计，平滑分析在流行几何学中的系统应用，NP难几何问题的多项式时间近似方案的设计，更广泛的影响：调查吸引学生从代表性不足的群体进入计算机科学和赞助研究机会的本科生从代表性不足的少数民族。通过新的入门和研究生课程的发展，教学和研究紧密结合。

Geometric representations of the physical world and of abstract information permeate science and engineering. Algorithms on geometric objects are central in mathematical programming, computer graphics, robotics, data mining, information retrieval, computational structural biology, scientific computing, and machine learning. This research spans the current agenda in geometric algorithm design and addresses fundamental problems whose resolution can impact the aforementioned fields.The research pursues four key themes: The design of novel algorithms for linear programming and related polytope-theoretic problems in computer science, a systematic application of smoothed analysis to popular geometric heuristics, the design of polynomial time approximation schemes for NP-hard geometric problems, and a resolution of the remaining issues in the theory of arrangements.Broader impacts: The investigator attracts students from underrepresented groups into computer science and sponsors research opportunities for undergraduate students from underrepresented minorities. Teaching and research are tightly integrated through the development of new introductory and graduate courses.