Джон Э. Хершбергер (родился в 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 ) треугольников; на запросы стрельбы лучами можно ответить, просто пройдя от треугольника к треугольнику, пока луч запроса не попадет на границу многоугольника.
Кинетические структуры данных , предложенные Леонидасом Гибасом , Жюльеном Башем и Хершбергером, были и продолжают быть влиятельными в вычислительной геометрии. Работая самостоятельно и с различными соавторами, Джон разработал кинетические структуры данных для сохранения протяженности движущихся точек; связанных компонентов движущихся единичных дисков, прямоугольников и гиперкубов; кластеров для наборов движущихся точек; и структур данных для обнаружения столкновений между многоугольниками в движении.