John E. Hershberger (nacido en 1959) es un científico informático y profesional de software estadounidense, ingeniero principal en Mentor Graphics Corporation desde 1993. Es conocido por su investigación en geometría computacional e ingeniería de algoritmos .
Hershberger realizó sus estudios de grado en el Instituto Tecnológico de California , donde se graduó en 1981. Obtuvo un doctorado en Ciencias de la Computación en la Universidad de Stanford en 1987 bajo la supervisión de Leonidas Guibas . Fue miembro del personal técnico del Centro de Investigación de Sistemas de Digital Equipment Corporation en Palo Alto , California , hasta 1993, cuando se unió a Mentor Graphics como ingeniero de software y líder de proyectos.
Fue presidente del comité de programa del 25º Simposio ACM sobre Geometría Computacional en 2009, y copresidente del comité de programa del Taller sobre Ingeniería de Algoritmos y Experimentos (ALENEX) en 2009. [1] [2]
En 2012 fue elegido miembro de la Association for Computing Machinery "por sus contribuciones a la computación geométrica y al diseño de herramientas para circuitos integrados". [3]
John Hershberger ha contribuido significativamente a la geometría computacional y a la comunidad de algoritmos desde mediados de la década de 1980. Su primer trabajo se centró en los caminos más cortos y la visibilidad. Con Leonidas Guibas y por sí mismo, ideó algoritmos óptimos de tiempo lineal para calcular polígonos de visibilidad , árboles de caminos más cortos , gráficos de visibilidad y estructuras de datos para consultas de caminos más cortos en tiempo logarítmico en polígonos simples. Con Jack Snoeyink, extendió los algoritmos para polígonos simples para calcular caminos más cortos homotópicos entre obstáculos poligonales en el plano . También inventó algoritmos paralelos para resolver varios problemas de caminos más cortos y visibilidad .
Uno de los logros más significativos de este período es su algoritmo (trabajo conjunto con Subhash Suri ) para calcular las rutas más cortas entre obstáculos poligonales en el plano utilizando solo un tiempo O( n log n ) . Este algoritmo fue una gran mejora con respecto al tiempo de ejecución aproximadamente cuadrático que se podía lograr con los métodos basados en gráficos de visibilidad y resolvió un problema que había estado abierto y se había estudiado intensamente durante años.
La estructura de datos para "Disparo de rayos peatonales", ideada por John y Subhash Suri , responde a consultas de disparo de rayos en un polígono simple . Consiste en una triangulación especial de modo que cualquier segmento de línea dentro del polígono intersecta solo O(log n ) triángulos; las consultas de disparo de rayos se pueden responder simplemente caminando de un triángulo a otro hasta que el rayo de consulta llegue al límite del polígono.
Las estructuras de datos cinéticos propuestas por Leonidas Guibas , Julien Basch y Hershberger han sido y siguen siendo influyentes en la geometría computacional. Trabajando solo y con una variedad de coautores, John ideó estructuras de datos cinéticos para mantener la extensión de los puntos en movimiento; los componentes conectados de discos unitarios móviles, rectángulos e hipercubos; clústeres para conjuntos de puntos en movimiento; y estructuras de datos para detectar colisiones entre polígonos en movimiento.