Кеннет Л. Кларксон - Kenneth L. Clarkson

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

Кеннет Ли Кларксон американец специалист в области информатики известен своими исследованиями в вычислительная геометрия. Он научный сотрудник Исследовательский центр IBM в Альмадене, и соредактор Журнал вычислительной геометрии.[1]

биография

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

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

Исследование

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

Его самая цитируемая статья с Петр Шор, использует случайная выборка разработать оптимальные рандомизированные алгоритмы для нескольких проблем построения геометрических структур, как продолжение ранее написанной одним автором статьи Кларксона по той же теме.[4][5]Включает в себя алгоритмы поиска всех пересечения между набором отрезки линии в самолете в ожидаемое время , находя диаметр набора точки в трех измерениях в ожидаемое время , и построение выпуклый корпус из указывает в -размерный Евклидово пространство в ожидаемое время . В той же статье также используется случайная выборка для доказательства границ в дискретная геометрия, и, в частности, дать жесткие границы на количество ≤k-наборы.

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

Награды и отличия

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

Рекомендации

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

внешняя ссылка