John Hershberger

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.