David Kirkpatrick

Prof. David Kirkpatrick is Professor Emeritus in Computer Science. His research deals with topics in theoretical computer science. He is particularly interested in computational complexity, specifically the determination or characterization of the inherent computational difficulty of solving certain specific problems – or families of problems – on realistic models of computation.

The problems that he is concerned with are fundamental combinatorial problems (including sorting and a number of basic graph theoretic problems, such as graph matchings and their generalizations) and geometric problems (including convex hulls, Voronoi diagrams, point location, geometric intersection, facility location, and motion planning) that have widespread applications.