Kenneth Lee Clarkson is an American computer scientist known for his research in computational geometry. He is a researcher at the IBM Almaden Research Center, and co-editor-in-chief of Discrete and Computational Geometry[1] and of the Journal of Computational Geometry.[2]
Clarkson received his Ph.D. from Stanford University in 1984, under the supervision of Andrew Yao.[3] Until 2007 he worked for Bell Labs.[4]
In 1998 he was co-chair of the ACM Symposium on Computational Geometry.
Clarkson's primary research interests are in computational geometry.
His most highly cited paper, with Peter Shor, uses random sampling to devise optimal randomized algorithms for several problems of constructing geometric structures, following up on an earlier singly-authored paper by Clarkson on the same subject.[5] [6] It includes algorithms for finding all
k
n
O(k+nlogn)
n
O(nlogn)
n
d
O(n\lfloor+nlogn)
Clarkson has also written highly cited papers on the complexity of arrangements of curves and surfaces,[7] nearest neighbor search,[8] [9] motion planning,[10] and low-dimensional linear programming and LP-type problems.[11]
In 2008 Clarkson was named ACM Fellow for his "contributions to computational geometry."[12]