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