David Kirkpatrick

Professor
Email: kirk [at] cs [dot] ubc [dot] ca
Office: ICCS X839
Phone: 604-822-4777
Lab(s):

Curriculum Vitae

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).

Keywords

combinatorial algorithms
computational complexity
computational geometry
parallel computation
distributed computation

Interests

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.

Selected Publications

Kirkpatrick, D. G., "Generalizing Ham Sandwich Cuts to Equitable Subdivisions", Discrete and Computational Geometry, to appear. (With S. Bespamyatnikh and J. Snoeyink).

Kirkpatrick, D. G. "Optimal Algorithms for Probabalistic Solitude Detection on Anonymous Rings", Journal of Algorithms, 23, 1997, pp. 291-328. (With L. Higham, K. Abrahamson And A. Adler).

Kirkpatrick, D. G. "Rounding in Symmetric Matrices and Undirected Graphs", Discrete Applied Mathematics, 70, 1996, pp. 1-21. (With P. Hell).

Kirkpatrick, D. G. "A Compact Piecewise-Linear Voronoi Diagram for Convex Sites in the Plane", Discrete and Computational Geometry, 15, 1996, pp. 73-105. (With M. Mcallister and J. Snoeyink).

Latest CS Courses

2013 Winter

CPSC 420  –  Advanced Algorithms Design and Analysis

2012 Winter

CPSC 420  –  Advanced Algorithms Design and Analysis
CPSC 516  –  Computational Geometry

2011 Winter

CPSC 420  –  Advanced Algorithms Design and Analysis

2010 Winter

CPSC 420  –  Advanced Algorithms Design and Analysis

a place of mind, The University of British Columbia

 

ICICS/CS Building 201-2366 Main Mall
Vancouver, B.C. V6T 1Z4 Canada
Tel: 604-822-3061 | Fax: 604-822-5485
General: help@cs.ubc.ca
Undergrad program: undergrad-info@cs.ubc.ca
Graduate program: grad-info@cs.ubc.ca

Emergency Procedures | Accessibility | Contact UBC | © Copyright The University of British Columbia