David G. Kirkpatrick
Encyclopedia
David Galer Kirkpatrick is a professor of computer science
at the University of British Columbia
. He is known for the Kirkpatrick–Seidel algorithm
and his work on Polygon triangulation
, and for co-inventing α-shapes and the β-skeleton
. He received his PhD from the University of Toronto
in 1974.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
at the University of British Columbia
University of British Columbia
The University of British Columbia is a public research university. UBC’s two main campuses are situated in Vancouver and in Kelowna in the Okanagan Valley...
. He is known for the Kirkpatrick–Seidel algorithm
Kirkpatrick–Seidel algorithm
The Kirkpatrick–Seidel algorithm, called by its authors "the ultimate planar convex hull algorithm" is an algorithm for computing the convex hull of a set of points in the plane, with O time complexity, where n is the number of input points and h is the number of points in the hull...
and his work on Polygon triangulation
Polygon triangulation
In computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P....
, and for co-inventing α-shapes and the β-skeleton
Beta skeleton
In computational geometry and geometric graph theory, a β-skeleton or beta skeleton is an undirected graph defined from a set of points in the Euclidean plane...
. He received his PhD from the University of Toronto
University of Toronto
The University of Toronto is a public research university in Toronto, Ontario, Canada, situated on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution of higher learning in Upper Canada...
in 1974.
Works
- Dissertation: Topics in the Complexity of Combinational Algorithms, University of Toronto 1974