Leonidas J. Guibas
Encyclopedia
Leonidas John Guibas is a professor of computer science
at Stanford University
, where he heads the geometric computation group and is a member of the computer graphics and artificial intelligence laboratories. Guibas was a student of Donald Knuth
at Stanford, where he received his Ph.D. in 1976. He has worked for several industrial research laboratories, and joined the Stanford faculty in 1984. He was program chair for the ACM
Symposium on Computational Geometry
in 1996, is a Fellow
of the ACM, and was awarded the ACM–AAAI Allen Newell
award for 2007 “for his pioneering contributions in applying algorithms to a wide range of computer science disciplines.“ He has Erdős number
2 due to his collaborations with Boris Aronov, Andrew Odlyzko
, János Pach
, Richard M. Pollack, Endre Szemerédi
, and Frances Yao
. The research contributions he is known for include finger tree
s, red-black tree
s, fractional cascading
, the Guibas–Stolfi
algorithm for Delaunay triangulation
, an optimal data structure for point location
, the quad-edge data structure for representing planar subdivisions, Metropolis light transport
, and kinetic data structures for keeping track of objects in motion.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
at Stanford University
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...
, where he heads the geometric computation group and is a member of the computer graphics and artificial intelligence laboratories. Guibas was a student of Donald Knuth
Donald Knuth
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
at Stanford, where he received his Ph.D. in 1976. He has worked for several industrial research laboratories, and joined the Stanford faculty in 1984. He was program chair for the ACM
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
Symposium on Computational Geometry
Symposium on Computational Geometry
The Annual Symposium on Computational Geometry is an academic conference in computational geometry. It was founded in 1985, and in most but not all of its years it has been sponsored by the Association for Computing Machinery's SIGACT and SIGGRAPH special interest groups.A 2010 assessment of...
in 1996, is a Fellow
Fellow
A fellow in the broadest sense is someone who is an equal or a comrade. The term fellow is also used to describe a person, particularly by those in the upper social classes. It is most often used in an academic context: a fellow is often part of an elite group of learned people who are awarded...
of the ACM, and was awarded the ACM–AAAI Allen Newell
Allen Newell
Allen Newell was a researcher in computer science and cognitive psychology at the RAND corporation and at Carnegie Mellon University’s School of Computer Science, Tepper School of Business, and Department of Psychology...
award for 2007 “for his pioneering contributions in applying algorithms to a wide range of computer science disciplines.“ He has Erdős number
Erdos number
The Erdős number describes the "collaborative distance" between a person and mathematician Paul Erdős, as measured by authorship of mathematical papers.The same principle has been proposed for other eminent persons in other fields.- Overview :...
2 due to his collaborations with Boris Aronov, Andrew Odlyzko
Andrew Odlyzko
Andrew Michael Odlyzko is a mathematician and a former head of the University of Minnesota's Digital Technology Center.In the field of mathematics he has published extensively on analytic number theory, computational number theory, cryptography, algorithms and computational complexity,...
, János Pach
János Pach
János Pach is a mathematician and computer scientist working in the fields of combinatorics and discrete and computational geometry...
, Richard M. Pollack, Endre Szemerédi
Endre Szemerédi
Endre Szemerédi is a Hungarian mathematician, working in the field of combinatorics and theoretical computer science. He is the State of New Jersey Professor of computer science at Rutgers University since 1986...
, and Frances Yao
Frances Yao
Frances Foong Yao is professor and head of the department of computer science at the City University of Hong Kong.After receiving a B.S. in mathematics from National Taiwan University in 1969, Yao did her Ph.D. studies under the supervision of Michael J. Fischer at the Massachusetts Institute of...
. The research contributions he is known for include finger tree
Finger tree
A finger tree is a purely functional data structure used in efficiently implementing other functional data structures. A finger tree gives amortized constant time access to the "fingers" of the tree, where data is stored, and the internal nodes are labeled in some way as to provide the...
s, red-black tree
Red-black tree
A red–black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer and named "symmetric binary B-tree," but acquired its modern name in a paper in 1978 by...
s, fractional cascading
Fractional cascading
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 Guibas–Stolfi
Jorge Stolfi
Jorge Stolfi is a full professor of computer science at the State University of Campinas, working in computer vision, image processing, splines and other function approximation methods, graph theory, computational geometry, and several other fields...
algorithm for Delaunay triangulation
Delaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
, an optimal data structure for point location
Point location
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 , motion planning, and computer aided design ....
, the quad-edge data structure for representing planar subdivisions, Metropolis light transport
Metropolis light transport
The Metropolis light transport is a SIGGRAPH 1997 paper by Eric Veach and Leonidas J. Guibas, describing an application of a variant of the Monte Carlo method called the Metropolis-Hastings algorithm to the rendering equation for generating images from detailed physical descriptions of three...
, and kinetic data structures for keeping track of objects in motion.