John Hershberger

John E. Hershberger (born 1959) is an American computer scientist and software professional, a principal engineer at Mentor Graphics Corporation since 1993. He is known for his research in computational geometry and algorithm engineering.

Biography Hershberger did his undergraduate studies at the California Institute of Technology, graduating in 1981. He earned a Ph.D. in Computer science from Stanford University in 1987 under the supervision of Leonidas Guibas. He was a member of the technical staff at the Digital Equipment Corporation Systems Research Center in Palo Alto, California, until 1993, when he joined Mentor Graphics as a software engineer and project leader.

He was program committee chair for the 25th ACM Symposium on Computational Geometry in 2009, and program committee co-chair for the Workshop on Algorithm Engineering and Experiments (ALENEX) in 2009.

In 2012 he was elected as a fellow of the Association for Computing Machinery "for contributions to geometric computing and to design tools for integrated circuits".

He lives in Tigard, Oregon.

Contributions

Computational geometry

John Hershberger has been a significant contributor to computational geometry and the algorithms community since the mid-1980s. His earliest work focused on shortest paths and visibility. With Leonidas Guibas and by himself, he devised optimal linear-time algorithms to compute visibility polygons, shortest path trees, visibility graphs, and data structures for logarithmic-time shortest path queries in simple polygons. With Jack Snoeyink he extended the algorithms for simple polygons to compute homotopic shortest paths among polygonal obstacles in the plane. He also invented parallel algorithms to solve several shortest path and visibility problems.

One of the most significant achievement of this period is his algorithm (joint work with Subhash Suri) to compute shortest paths among polygonal obstacles in the plane using only O(n log n) time. This algorithm was a vast improvement over the roughly quadratic running time achievable by visibility-graph-based methods, and resolved a problem that had been open and intensely studied for years.

Data structure for "Pedestrian ray shooting", devised by John and Subhash Suri, answers ray shooting queries in a simple polygon. It consists of a special triangulation such that any line segment inside the polygon intersects only O(log n) triangles; ray shoot-ing queries can be answered simply by walking from triangle to triangle until the query ray hits the polygon boundary.

Kinetic data structures, proposed by Leonidas Guibas, Julien Basch and Hershberger, have been and continue to be influential in computational geometry. Working by himself and with a variety of co-authors, John devised kinetic data structures to maintain the extent of moving points; the connected components of moving unit disks, rectangles, and hypercubes; clusters for sets of moving points; and data structures to detect collisions between polygons in motion.

Selected publications . . . . .