David Kirkpatrick

Professor Emeritus

Office Phone #

Academic Information

B.Sc., University of British Columbia (1970); Ph.D., Univ. of Toronto (1974); Visiting Assistant Professor, Cornell (1974-75); Assistant Professor, Simon Fraser University (1975-78); Assistant Professor, University of British Columbia (1978); Associate Professor, University of British Columbia (1982); Professor, University of British Columbia (1986-); Fellow, British Columbia Advanced Systems Institute (1988-); Associate Dean, Faculty of Graduate Studies (1996-98).

Research Areas

computational geometry

Research Groups


My research deals with topics in theoretical computer science. I am 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 I am 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.

While much of my research is based on a standard sequential deterministic model of computation, I am also interested in both parallel and distributed models of computation and the use of probabilistic algorithms.


2020 Winter
CPSC 320 - Intermediate Algorithm Design and Analysis
CPSC 515 - Computational Robotics
2014 Winter
CPSC 420 - Advanced Algorithms Design and Analysis
CPSC 500 - Fundamentals of Algorithm Design and Analysis