Джон Хершбергер - John Hershberger

Джон Э. Хершбергер (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.

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

  1. ^ Материалы 25-го ежегодного симпозиума по вычислительной геометрии из электронной библиотеки ACM
  2. ^ ALENEX09 с сайта siam.org
  3. ^ Ссылка на награду участника ACM, получено 22 января 2013.

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