 |
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.
|
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.
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. [1] [2]
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". [3]
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.
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity.
The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided design (CAD).
A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.
In computational geometry and robot motion planning, a visibility graph is a graph of intervisible locations, typically for a set of points and obstacles in the Euclidean plane. Each node in the graph represents a point location, and each edge represents a visible connection between them. That is, if the line segment connecting two locations does not pass through any obstacle, an edge is drawn between them in the graph. When the set of locations lies in a line, this can be understood as an ordered series. Visibility graphs have therefore been extended to the realm of time series analysis.
The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem:
In computer science, fractional cascading is a technique to speed up a sequence of binary searches for the same value in a sequence of related data structures. The first binary search in the sequence takes a logarithmic amount of time, as is standard for binary searches, but successive searches in the sequence are faster. The original version of fractional cascading, introduced in two papers by Chazelle and Guibas in 1986, combined the idea of cascading, originating in range searching data structures of Lueker (1978) and Willard (1978), with the idea of fractional sampling, which originated in Chazelle (1983). Later authors introduced more complex forms of fractional cascading that allow the data structure to be maintained as the data changes by a sequence of discrete insertion and deletion events.
In Euclidean plane geometry, a pseudotriangle (pseudo-triangle) is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation (pseudo-triangulations) is a partition of a region of the plane into pseudotriangles, and a pointed pseudotriangulation is a pseudotriangulation in which at each vertex the incident edges span an angle of less than π.
The Euclidean shortest path problem is a problem in computational geometry: given a set of polyhedral obstacles in a Euclidean space, and two points, find the shortest path between the points that does not intersect any of the obstacles.
The dynamic convex hull problem is a class of dynamic problems in computational geometry. The problem consists in the maintenance, i.e., keeping track, of the convex hull for input data undergoing a sequence of discrete changes, i.e., when input data elements may be inserted, deleted, or modified. It should be distinguished from the kinetic convex hull, which studies similar problems for continuously moving points. Dynamic convex hull problems may be distinguished by the types of the input data and the allowed types of modification of the input data.
In computational geometry, the visibility polygon or visibility region for a point p in the plane among obstacles is the possibly unbounded polygonal region of all points of the plane visible from p. The visibility polygon can also be defined for visibility from a segment, or a polygon. Visibility polygons are useful in robotics, video games, and in various optimization problems such as the facility location problem and the art gallery problem.
In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain is a curve specified by a sequence of points called its vertices. The curve itself consists of the line segments connecting the consecutive vertices.
Leonidas John Guibas is the Paul Pigott Professor of Computer Science and Electrical Engineering at Stanford University. He heads the Geometric Computation group in the Computer Science Department.
Kenneth Lee Clarkson is an American computer scientist known for his research in computational geometry. He is a researcher at the IBM Almaden Research Center, and co-editor-in-chief of the Journal of Computational Geometry.
David Mount is a professor at the University of Maryland, College Park department of computer science whose research is in computational geometry.
Subhash Suri is an Indian-American computer scientist, a professor at the University of California, Santa Barbara. He is known for his research in computational geometry, computer networks, and algorithmic game theory.
A kinetic closest pair data structure is a kinetic data structure that maintains the closest pair of points, given a set P of n points that are moving continuously with time in a metric space. While many efficient algorithms were known in the static case, they proved hard to kinetize, so new static algorithms were developed to solve this problem.
A kinetic triangulation data structure is a kinetic data structure that maintains a triangulation of a set of moving points. Maintaining a kinetic triangulation is important for applications that involve motion planning, such as video games, virtual reality, dynamic simulations and robotics.
The k shortest path routing problem is a generalization of the shortest path routing problem in a given network. It asks not only about a shortest path but also about next k−1 shortest paths. A variation of the problem is the loopless k shortest paths.
Tetsuo Asano is a Japanese computer scientist, the president of the Japan Advanced Institute of Science and Technology. His main research interest is in computational geometry.
In discrete geometry and computational geometry, the relative convex hull or geodesic convex hull is an analogue of the convex hull for the points inside a simple polygon or a rectifiable simple closed curve.
| General | |
|---|---|
| National libraries | |
| Scientific databases | |
