CAREER: Fundamental Geometric Algorithms

Stanford University, Stanford CA

Investigators

Abstract

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.