Kenneth L. Clarkson
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 the Journal of 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. It includes algorithms for finding all intersections among a set of line segments in the plane in expected time , finding the diameter of a set of points in three dimensions in expected time , and constructing the convex hull of points in -dimensional Euclidean space in expected time . The same paper also uses random sampling to prove bounds in discrete geometry, and in particular to give tight bounds on the number of ≤k-sets.
Clarkson has also written highly cited papers on the complexity of arrangements of curves and surfaces, nearest neighbor search, motion planning, and low-dimensional linear programming and LP-type problems.
Awards and honors
- Editorial team, Journal of Computational Geometry. Retrieved 2009-05-30.
- TCS Genealogy, Association for Computing Machinery.
- Clarkson's page at Bell Labs, retrieved January 15, 2009.
- Clarkson, Kenneth L. (1987), "New applications of random sampling in computational geometry", Discrete and Computational Geometry, 2 (2): 195–222, doi:10.1007/BF02187879, MR 884226.
- Clarkson, Kenneth L.; Shor, Peter W. (1989), "Applications of random sampling in computational geometry. II", Discrete and Computational Geometry, 4 (5): 387–421, doi:10.1007/BF02187740, MR 1014736.
- Clarkson, Kenneth L.; Edelsbrunner, Herbert; Guibas, Leonidas J.; Sharir, Micha; Welzl, Emo (1990), "Combinatorial complexity bounds for arrangements of curves and spheres", Discrete and Computational Geometry, 5 (2): 99–160, doi:10.1007/BF02187783, MR 1032370.
- Clarkson, Kenneth L. (1988), "A randomized algorithm for closest-point queries", SIAM Journal on Computing, 17 (4): 830–847, doi:10.1137/0217052, MR 953296.
- Clarkson, K. L. (1999), "Nearest neighbor queries in metric spaces", Discrete and Computational Geometry, 22 (1): 63–93, doi:10.1007/PL00009449, MR 1692615.
- Clarkson, K. (1987), "Approximation algorithms for shortest path motion planning", Proc. 19th ACM Symposium on Theory of Computing, pp. 56–65, doi:10.1145/28395.28402.
- Clarkson, Kenneth L. (1995), "Las Vegas algorithms for linear and integer programming when the dimension is small", Journal of the ACM, 42 (2): 488–499, doi:10.1145/201019.201036, MR 1409744.
- ACM Fellow citation.