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

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

Биография

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

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

Исследовать

Основные исследовательские интересы Кларксона связаны с вычислительной геометрией .

Его наиболее цитируемая статья, написанная совместно с Питером Шором , использует случайную выборку для разработки оптимальных рандомизированных алгоритмов для нескольких задач построения геометрических структур, продолжая более раннюю статью Кларксона, написанную одним автором, на ту же тему. ^[5]^[6]Он включает в себя алгоритмы поиска всех $k$ пересечения множества $n$ сегменты прямых на плоскости в ожидаемое время $O(k+n\log n)$ , найдя диаметр набора $n$ точки в трех измерениях в ожидаемое время $O(n\log n)$ и построив выпуклую оболочку $n$ указывает на $d$ -мерное евклидово пространство в ожидаемом времени $O(n^{\lfloor d/2\rfloor }+n\log n)$ . В той же статье случайная выборка также используется для доказательства границ в дискретной геометрии и, в частности, для установления точных границ числа ≤ k -множеств .

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

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

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

Ссылки

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

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

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

[1] Редакторы , Дискретная и вычислительная геометрия. Проверено 31 января 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), "Алгоритмы аппроксимации для планирования движения по кратчайшему пути", Proc. 19-й симпозиум ACM по теории вычислений , стр. 56–65, doi : 10.1145/28395.28402 , S2CID 12206444 .

[11] Кларксон, Кеннет Л. (1995), «Алгоритмы Лас-Вегаса для линейного и целочисленного программирования при малых размерностях», Journal of the ACM , 42 (2): 488–499, doi : 10.1145/201019.201036 , MR 1409744 , S2CID 6953625 .

[12] Цитата о награде , член ACM .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]