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.