David Galer Kirkpatrick ist ein kanadischer Informatiker und emeritierter Professor für Informatik an der University of British Columbia, Kanada.

Leben

Kirkpatrick erlangte 1970 den Bachelor-Abschluss an der University of British Columbia. Er promovierte 1974 an der University of Toronto, Ontario, Kanada. 1974/1975 lehrte er als Visiting Assistant Professor in Cornell und anschließend von 1975 bis 1978 als Assistant Professor an der Simon Fraser University. 1978 wurde er Assistant Professor an der University of British Columbia und stieg dort 1982 zum Associate Professor und 1986 zum Professor auf. Von 1996 bis 1998 war er stellvertretender Dean der Fakultät für Graduate Studies. Er ist emeritiert, zuletzt hielt er 2014 Vorlesungen über Algorithmen-Design und Analysis.

Kirkpatrick ist bekannt für den Kirkpatrick-Seidel-Algorithmus, den er 1986 zusammen mit Raimund Seidel entwickelte. Der Algorithmus dient der Berechnung der konvexen Hülle in der Ebene und hat eine Laufzeit von ${\displaystyle {\mathcal {O}}(n\log h)}$, wobei ${\displaystyle h<=n}$ die Anzahl der Punkte angibt, die auf der Hülle liegen.

Seit 2009 ist Kirkpatrick Fellow der Royal Society of Canada.

Werk (Auswahl)

• 1974: Dissertation: Topics in the Complexity of Combinatorial Algorithms, University of Toronto.
• mit Raimund Seidel: The Ultimate Planar Convex Hull Algorithm? In: SIAM Journal on Computing. 1986, Band 15, Heft 1, S. 287–299, doi:10.1137/0215021.

Weblinks

• David Galer Kirkpatrick im Mathematics Genealogy Project (englisch)
• David Kirkpatrick, Professor Emeritus an der University of British Columbia