Kenneth Clarkson

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 del 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. desde Universidad 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 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. ^{[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 el casco convexo de puntos en - Espacio euclidiano dimensional en el tiempo esperado . El mismo artículo también utiliza muestreo aleatorio para probar 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 la disposición 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 tipo LP . ^[11]

Premios y honores

En 2008, Clarkson fue nombrado miembro de 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, Revista de geometría computacional. Consultado el 31 de enero de 2024.
3. TCS Genealogía, Asociación de Maquinaria de Computación .
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 computacional y discreta , 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 computacional y discreta , 4 (5): 387–421, doi : 10.1007/BF02187740 , MR  1014736.
7. Clarkson, Kenneth L.; Edelsbrunner, Herbert ; Guibas, Leónidas J .; Sharir, Micha ; Welzl, Emo (1990), "Límites de complejidad combinatoria para disposiciones 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 del 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 computacional y discreta , 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 el camino más corto", Proc. XIX 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. Mención del premio, miembro de ACM .

enlaces externos

• Página web de Clarkson en IBM