Кеннет Л. Кларксон

Американский учёный-компьютерщик

Кен Кларксон на SoCG 2011

Кеннет Ли Кларксон — американский учёный-компьютерщик , известный своими исследованиями в области вычислительной геометрии . Он является исследователем в исследовательском центре IBM Almaden и соредактором журнала Discrete and Computational Geometry ^[1] и журнала Journal of Computational Geometry ^[2] .

Биография

Кларксон получил степень доктора философии в Стэнфордском университете в 1984 году под руководством Эндрю Яо . ^[3] До 2007 года он работал в Bell Labs . ^[4]

В 1998 году он был сопредседателем симпозиума ACM по вычислительной геометрии .

Исследовать

Основные научные интересы Кларксона лежат в области вычислительной геометрии .

Его наиболее цитируемая статья, совместно с Питером Шором , использует случайную выборку для разработки оптимальных рандомизированных алгоритмов для нескольких задач построения геометрических структур, продолжая более раннюю статью Кларксона, написанную им в одиночку, по той же теме. ^{[5] [6]} Она включает алгоритмы для нахождения всех пересечений между набором отрезков прямых на плоскости за ожидаемое время , нахождения диаметра набора точек в трех измерениях за ожидаемое время и построения выпуклой оболочки точек в -мерном евклидовом пространстве за ожидаемое время . Та же статья также использует случайную выборку для доказательства границ в дискретной геометрии и, в частности, для указания строгих границ на число ≤ k -множеств . ${\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)}$

Кларксон также написал часто цитируемые статьи о сложности расположений кривых и поверхностей, ^[7] поиске ближайшего соседа , ^{[8] [9]} планировании движения , ^[10] и маломерном линейном программировании и задачах типа ЛП . ^[11]

Награды и почести

В 2008 году Кларксону было присвоено звание члена ACM за его «вклад в вычислительную геометрию». ^[12]

Ссылки

1. Редакторы, Дискретная и вычислительная геометрия. Получено 31.01.2024.
2. Редакционная группа, Журнал вычислительной геометрии. Получено 31 января 2024 г.
3. TCS Genealogy, Ассоциация вычислительной техники .
4. Страница Кларксона в Bell Labs. Архивировано 24 октября 2008 г. на Wayback Machine , получено 15 января 2009 г.
5. Кларксон, Кеннет Л. (1987), «Новые приложения случайной выборки в вычислительной геометрии», Дискретная и вычислительная геометрия , 2 (2): 195–222, doi : 10.1007/BF02187879 , MR  0884226.
6. Кларксон, Кеннет Л.; Шор, Питер В. (1989), «Применение случайной выборки в вычислительной геометрии. II», Дискретная и вычислительная геометрия , 4 (5): 387–421, doi : 10.1007/BF02187740 , MR  1014736.
7. Кларксон, Кеннет Л.; Эдельсбруннер, Герберт ; Гибас, Леонидас Дж .; Шарир, Миха ; Вельцль, Эмо (1990), «Комбинаторные границы сложности для расположений кривых и сфер», Дискретная и вычислительная геометрия , 5 (2): 99–160, doi : 10.1007/BF02187783 , MR  1032370.
8. Кларксон, Кеннет Л. (1988), «Рандомизированный алгоритм для запросов на ближайшую точку», SIAM Journal on Computing , 17 (4): 830–847, doi :10.1137/0217052, MR  0953296.
9. Кларксон, К. Л. (1999), «Запросы ближайшего соседа в метрических пространствах», Дискретная и вычислительная геометрия , 22 (1): 63–93, doi : 10.1007/PL00009449 , MR  1692615.
10. Кларксон, К. (1987), «Аппроксимационные алгоритмы для планирования движения по кратчайшему пути», Труды 19-го симпозиума ACM по теории вычислений , стр. 56–65, doi : 10.1145/28395.28402 , S2CID  12206444.
11. Кларксон, Кеннет Л. (1995), «Алгоритмы Лас-Вегаса для линейного и целочисленного программирования при малой размерности», Журнал ACM , 42 (2): 488–499, doi : 10.1145/201019.201036 , MR  1409744, S2CID  6953625.
12. Награда, член ACM .

Внешние ссылки

• Веб-страница Кларксона в IBM