David Kirkpatrick David Kirkpatrick Combinatorics; computational geometry; theory of computation.
My research deals with topics in theoretical computer science. I am particularly interested in computational complexity, specifically the determinat ion or characterization of the inherent computational difficulty of solving cert ain specific problems - or families of problems - on realistic models of computa tion.
The problems that I am concerned with are fundamental combinatorial (including sorting and a number of basic graph theoretic problems) and geometric (including convex hulls, Voronoi diagrams, point location, geometric intersection, and motion planning) problems that have widespread applications.
While much of my research is based on a standard sequential deterministic model of computation, I have recently become more interested in both parallel and distributed models of computation and the use of probabilistic algorithms.