Джон Хершбергер
 |
Джон Э. Хершбергер (род. 1959) — американский учёный-компьютерщик и специалист по программному обеспечению, главный инженер Mentor Graphics Corporation с 1993 года. Он известен своими исследованиями в области вычислительной геометрии и разработки алгоритмов .
Биография
[ редактировать ]Хершбергер учился на бакалавриате в Калифорнийском технологическом институте , который окончил в 1981 году. Он получил степень доктора философии. Получил степень бакалавра компьютерных наук в Стэнфордском университете в 1987 году под руководством Леонидаса Гибаса . Он был членом технического персонала в Digital Equipment Corporation Центре системных исследований в Пало-Альто , Калифорния , до 1993 года, когда он присоединился к Mentor Graphics в качестве инженера-программиста и руководителя проекта.
Он был председателем программного комитета 25-го симпозиума ACM по вычислительной геометрии в 2009 году и сопредседателем программного комитета Семинара по разработке алгоритмов и экспериментов (ALENEX) в 2009 году. [1] [2]
В 2012 году он был избран членом Ассоциации вычислительной техники «за вклад в геометрические вычисления и разработку инструментов для интегральных схем». [3]
Он живет в Тигарде , штат Орегон .
Взносы
[ редактировать ]Вычислительная геометрия
[ редактировать ]Джон Хершбергер внес значительный вклад в вычислительную геометрию и сообщество алгоритмов с середины 1980-х годов. Его ранние работы были посвящены кратчайшим путям и видимости. Вместе с Леонидасом Гибасом и самостоятельно он разработал оптимальные алгоритмы с линейным временем для вычисления полигонов видимости , деревьев кратчайших путей , графов видимости и структур данных для запросов кратчайшего пути с логарифмическим временем в простых многоугольниках. Совместно с Джеком Снойинком он расширил алгоритмы для простых многоугольников, чтобы вычислить гомотопические кратчайшие пути среди многоугольных препятствий на плоскости . Он также изобрел параллельные алгоритмы для решения нескольких поиска кратчайшего пути и задач видимости .
Одним из наиболее значительных достижений этого периода является его алгоритм (совместная работа с Субхашем Сури ) для вычисления кратчайших путей среди многоугольных препятствий на плоскости, используя всего лишь время O( n log n ) . Этот алгоритм был значительным улучшением по сравнению с примерно квадратичным временем выполнения , достижимым с помощью методов, основанных на графе видимости , и решил проблему, которая была открыта и интенсивно изучалась в течение многих лет.
Структура данных для «Пешеходной лучевой стрельбы», разработанная Джоном и Субхашем Сури , отвечает на запросы лучевой стрельбы в простом многоугольнике . Он состоит из специальной триангуляции , в которой любой отрезок линии внутри многоугольника пересекает только O(log n ) треугольников; На запросы лучевой стрельбы можно ответить, просто проходя от треугольника к треугольнику, пока луч запроса не достигнет границы многоугольника.
Кинетические структуры данных , предложенные Леонидасом Гибасом , Жюльеном Башем и Хершбергером, были и продолжают оказывать влияние на вычислительную геометрию. Работая самостоятельно и с различными соавторами, Джон разработал кинетические структуры данных, позволяющие сохранять масштаб движущихся точек; компоненты связности движущихся единичных дисков, прямоугольников и гиперкубов; кластеры для наборов движущихся точек; и структуры данных для обнаружения столкновений между движущимися полигонами.
Избранные публикации
[ редактировать ]- Гибас, Леонидас ; Хершбергер, Джон (1989), «Запросы оптимального кратчайшего пути в простом многоугольнике», Journal of Computer and System Sciences , 39 (2): 126–152, doi : 10.1016/0022-0000(89)90041-x .
- Хершбергер, Джон; Сури, Субхаш (1999), «Оптимальный алгоритм для поиска евклидовых кратчайших путей на плоскости» , SIAM Journal on Computing , 28 (6): 2215–2256, CiteSeerX 10.1.1.47.2037 , doi : 10.1137/S0097539795289604 , MR 1698954 .
- Баш, Жюльен; Гибас, Леонидас ; Хершбергер, Джон (1999), «Структуры данных для мобильных данных», Journal of Algorithms , 31 (1): 1–28, CiteSeerX 10.1.1.134.6921 , doi : 10.1006/jagm.1998.0988 , S2CID 8013433 .
- Хершбергер, Джон; Максель, Мэтт; Сури, Субхаш (2007), «Нахождение k кратчайших простых путей: новый алгоритм и его реализация», Транзакции ACM по алгоритмам , 3 (4), статья 45, doi : 10.1145/1290672.1290682 , S2CID 10703503 .
- Хершбергер, Джон (2008), «Улучшенное округление привязки с учетом выходных данных», Discrete and Computational Geometry , 39 (1–3): 298–318, doi : 10.1007/s00454-007-9015-0 .
Ссылки
[ редактировать ]Внешние ссылки
[ редактировать ]- Джон Хершбергер в Scholar Wiki
- Джон Хершбергер на DBLP библиографическом сервере
| Международный | |
|---|---|
| Национальный | |
| академики | |