Джон Хершбергер

Эта биография живого человека нуждается в дополнительных цитатах для проверки . Пожалуйста, помогите, добавив надежные источники . Спорный материал о живых людях, который не имеет или имеет плохие источники, должен быть немедленно удален из статьи и ее страницы обсуждения, особенно если он потенциально клеветнический . Найти источники:  "Джон Хершбергер" – новости  · газеты  · книги  · ученый  · JSTOR ( январь 2013 г. ) ( Узнайте, как и когда удалять это сообщение )

Джон Э. Хершбергер (родился в 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), «Запросы оптимального кратчайшего пути в простом многоугольнике», Журнал компьютерных и системных наук , 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), «Структуры данных для мобильных данных», Журнал алгоритмов , 31 (1): 1–28, CiteSeerX  10.1.1.134.6921 , doi :10.1006/jagm.1998.0988, S2CID  8013433.
• Хершбергер, Джон; Максель, Мэтт; Сури, Субхаш (2007), «Поиск k кратчайших простых путей: новый алгоритм и его реализация», ACM Transactions on Algorithms , 3 (4), Статья 45, doi : 10.1145/1290672.1290682, S2CID  10703503.
• Хершбергер, Джон (2008), «Улучшенное чувствительное к выходу округление», Дискретная и вычислительная геометрия , 39 (1–3): 298–318, doi : 10.1007/s00454-007-9015-0.

• Джон Хершбергер в Scholar Wiki
• Джон Хершбергер на библиографическом сервере DBLP