Kenneth L. Clarkson

Científico informático estadounidense

Ken Clarkson en SoCG 2011

Kenneth Lee Clarkson es un informático estadounidense conocido por sus investigaciones en geometría computacional . Es investigador en el IBM Almaden Research Center y coeditor jefe de Discrete and Computational Geometry ^[1] y del Journal of Computational Geometry ^[2] .

Biografía

Clarkson recibió su doctorado en la Universidad de Stanford en 1984, bajo la supervisión de Andrew Yao . ^[3] Hasta 2007 trabajó para Bell Labs . ^[4]

En 1998 fue copresidente del Simposio ACM sobre Geometría Computacional .

Investigación

Los principales intereses de investigación de Clarkson son la geometría computacional .

Su artículo más citado, con Peter Shor , utiliza un muestreo aleatorio para diseñar algoritmos aleatorios óptimos para varios problemas de construcción de estructuras geométricas, siguiendo un artículo anterior de un solo autor por Clarkson sobre el mismo tema. ^{[5] [6]} Incluye algoritmos para encontrar todas las intersecciones entre un conjunto de segmentos de línea en el plano en el tiempo esperado , encontrar el diámetro de un conjunto de puntos en tres dimensiones en el tiempo esperado y construir la envoltura convexa de puntos en el espacio euclidiano -dimensional en el tiempo esperado . El mismo artículo también utiliza un muestreo aleatorio para demostrar límites en geometría discreta y, en particular, para dar límites estrictos al número de ≤ k -conjuntos . ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle O(k+n\log n)}$ ${\displaystyle n}$ ${\displaystyle O(n\log n)}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle O(n^{\lfloor d/2\rfloor }+n\log n)}$

Clarkson también ha escrito artículos muy citados sobre la complejidad de los arreglos de curvas y superficies, ^[7] búsqueda del vecino más cercano , ^{[8] [9]} planificación del movimiento , ^{[10] y} programación lineal de baja dimensión y problemas de tipo LP . ^[11]

Premios y honores

En 2008, Clarkson fue nombrado miembro de la ACM por sus "contribuciones a la geometría computacional". ^[12]

Referencias

1. Editores, Geometría discreta y computacional. Consultado el 31 de enero de 2024.
2. Equipo editorial, Journal of Computational Geometry. Consultado el 31 de enero de 2024.
3. Genealogía TCS, Asociación para Maquinaria Computacional .
4. Página de Clarkson en Bell Labs Archivado el 24 de octubre de 2008 en Wayback Machine , consultado el 15 de enero de 2009.
5. 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.
6. 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.
7. 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.
8. Clarkson, Kenneth L. (1988), "Un algoritmo aleatorio para consultas de punto más cercano", SIAM Journal on Computing , 17 (4): 830–847, doi :10.1137/0217052, MR  0953296.
9. Clarkson, KL (1999), "Consultas de vecino más cercano en espacios métricos", Geometría discreta y computacional , 22 (1): 63–93, doi : 10.1007/PL00009449 , MR  1692615.
10. Clarkson, K. (1987), "Algoritmos de aproximación para la planificación del movimiento por la ruta más corta", Actas del 19.º Simposio ACM sobre teoría de la computación , págs. 56-65, doi : 10.1145/28395.28402 , S2CID  12206444.
11. 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.
12. Cita del premio, ACM Fellow .

Enlaces externos

• Página web de Clarkson en IBM