John E. Hershberger (nacido en 1959) es un científico informático y profesional de software estadounidense, ingeniero principal de Mentor Graphics Corporation desde 1993. Es conocido por su investigación en geometría computacional e ingeniería de algoritmos .
Biografía
Hershberger realizó sus estudios de pregrado en el Instituto de Tecnología de California , donde se graduó en 1981. Obtuvo un doctorado. en Ciencias de la Computación de 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 para el 25º Simposio de ACM sobre geometría computacional en 2009, y copresidente del comité de programa para el 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]
Contribuciones
Geometría Computacional
John Hershberger ha contribuido significativamente a la geometría computacional y 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 él mismo, ideó algoritmos óptimos de tiempo lineal para calcular polígonos de visibilidad , árboles de ruta más corta , gráficos de visibilidad y estructuras de datos para consultas de ruta más corta en tiempo logarítmico en polígonos simples. Con Jack Snoeyink extendió los algoritmos para polígonos simples para calcular las rutas homotópicas más cortas entre obstáculos poligonales en el avión . También inventó algoritmos paralelos para resolver varios problemas de visibilidad y rutas más cortas .
Uno de los logros más importantes de este período es su algoritmo (trabajo conjunto con Subhash Suri ) para calcular las trayectorias más cortas entre los obstáculos poligonales en el plano utilizando solo el tiempo O ( n log n ) . Este algoritmo supuso una gran mejora con respecto al tiempo de ejecución aproximadamente cuadrático que se podía conseguir mediante métodos basados en gráficos de visibilidad , y resolvió un problema que había estado abierto y estudiado intensamente durante años.
La estructura de datos para "Disparos de rayos peatonales", ideada por John y Subhash Suri , responde a las consultas de disparos de rayos en un polígono simple . Consiste en una triangulación especial tal que cualquier segmento de línea dentro del polígono interseca solo triángulos O (log n ); Las consultas sobre disparos 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; agrupaciones para conjuntos de puntos móviles; y estructuras de datos para detectar colisiones entre polígonos en movimiento.
Publicaciones Seleccionadas
- Guibas, Leonidas ; Hershberger, John (1989), "Consultas de ruta más corta óptima en un polígono simple", Journal of Computer and System Sciences , 39 (2): 126-152, doi : 10.1016 / 0022-0000 (89) 90041-x.
- Hershberger, John; Suri, Subhash (1999), "Un algoritmo óptimo para trayectos euclidianos más cortos en el plano" , SIAM Journal on Computing , 28 (6): 2215-2256, CiteSeerX 10.1.1.47.2037 , doi : 10.1137 / S0097539795289604 , MR 1698954.
- Basch, Julien; Guibas, Leonidas ; Hershberger, John (1999), "Estructuras de datos para datos móviles", Journal of Algorithms , 31 (1): 1–28, CiteSeerX 10.1.1.134.6921 , doi : 10.1006 / jagm.1998.0988.
- Hershberger, John; Maxel, Matt; Suri, Subhash (2007), "Encontrar las k rutas simples más cortas: un nuevo algoritmo y su implementación", Transacciones ACM sobre algoritmos , 3 (4), artículo 45, doi : 10.1145 / 1290672.1290682 , S2CID 10703503.
- Hershberger, John (2008), "Mejora del redondeo de ajuste sensible a la salida", Geometría discreta y computacional , 39 (1–3): 298–318, doi : 10.1007 / s00454-007-9015-0.
Referencias
- ^ Actas del vigésimo quinto simposio anual sobre geometría computacional de la biblioteca digital ACM
- ^ ALENEX09 de siam.org
- ^ Cita del premio ACM Fellow , consultado el 22 de enero de 2013.
enlaces externos
- John Hershberger en Scholar Wiki
- John Hershberger en el servidor de bibliografía DBLP