Kenneth Lee Clarkson es un informático estadounidense conocido por su investigación en geometría computacional . Es investigador del IBM Almaden Research Center y coeditor en jefe del Journal of Computational Geometry . [1]
Biografía
Clarkson recibió su Ph.D. de la Universidad de Stanford en 1984, bajo la supervisión de Andrew Yao . [2] Hasta 2007 trabajó para Bell Labs . [3]
En 1998 fue copresidente del Simposio ACM sobre Geometría Computacional .
Investigar
Los principales intereses de investigación de Clarkson son la geometría computacional .
Su artículo más citado, con Peter Shor , utiliza muestreo aleatorio para diseñar algoritmos aleatorios óptimos para varios problemas de construcción de estructuras geométricas, siguiendo un artículo anterior de Clarkson sobre el mismo tema. [4] [5] Incluye algoritmos para encontrar todos intersecciones entre un conjunto de segmentos de línea en el avión en el tiempo esperado, encontrando el diámetro de un conjunto de puntos en tres dimensiones en el tiempo esperado , y construyendo el casco convexo de puntos en -espacio euclidiano dimensional en tiempo esperado. El mismo documento también se utiliza el muestreo aleatorio para demostrar límites en geometría discreta , y en particular para dar límites ajustados del número de ≤ k conjuntos- .
Clarkson también ha escrito artículos muy citados sobre la complejidad de los arreglos de curvas y superficies, [6] búsqueda de vecino más cercano , [7] [8] planificación de movimiento , [9] y programación lineal de baja dimensión y problemas de tipo LP . [10]
Premios y honores
En 2008, Clarkson fue elegido miembro de la ACM por sus "contribuciones a la geometría computacional". [11]
Referencias
- ^ Equipo editorial , Revista de geometría computacional. Consultado el 30 de mayo de 2009.
- ^ Genealogía de TCS , Asociación de maquinaria informática .
- ^ Página de Clarkson en Bell Labs Archivado el 24 de octubre de 2008en Wayback Machine , consultado el 15 de enero de 2009.
- ^ Clarkson, Kenneth L. (1987), "Nuevas aplicaciones del muestreo aleatorio en geometría computacional", Geometría discreta y computacional , 2 (2): 195-222, doi : 10.1007 / BF02187879 , MR 0884226.
- ^ Clarkson, Kenneth L .; Shor, Peter W. (1989), "Aplicaciones del muestreo aleatorio en geometría computacional. II", Geometría discreta y computacional , 4 (5): 387–421, doi : 10.1007 / BF02187740 , MR 1014736.
- ^ Clarkson, Kenneth L .; Edelsbrunner, Herbert ; Guibas, Leonidas J .; Sharir, Micha ; Welzl, Emo (1990), "Límites de complejidad combinatoria para arreglos de curvas y esferas", Geometría discreta y computacional , 5 (2): 99-160, doi : 10.1007 / BF02187783 , MR 1032370.
- ^ Clarkson, Kenneth L. (1988), "Un algoritmo aleatorio para consultas del punto más cercano", SIAM Journal on Computing , 17 (4): 830–847, doi : 10.1137 / 0217052 , MR 0953296.
- ^ Clarkson, KL (1999), "Consultas de vecinos más cercanos en espacios métricos", Geometría discreta y computacional , 22 (1): 63–93, doi : 10.1007 / PL00009449 , MR 1692615.
- ^ Clarkson, K. (1987), "Algoritmos de aproximación para la planificación del movimiento de la trayectoria más corta", Proc. XIX Simposio ACM sobre Teoría de la Computación , págs. 56–65, doi : 10.1145 / 28395.28402 , S2CID 12206444.
- ^ Clarkson, Kenneth L. (1995), "Algoritmos de Las Vegas para programación lineal y entera cuando la dimensión es pequeña", Journal of the ACM , 42 (2): 488–499, doi : 10.1145 / 201019.201036 , MR 1409744 , S2CID 6953625.
- ^ Cita de miembro de ACM .
enlaces externos
- Página web de Clarkson en IBM