Herbert Edelsbrunner
Encyclopedia
Herbert Edelsbrunner is a computer scientist working in the field of computational geometry
, the Arts & Science Professor of Computer Science and Mathematics at Duke University
, Professor at the Institute of Science and Technology Austria
(IST Austria), and the co-founder of Geomagic, Inc. He was the first of only two computer scientists to win the National Science Foundation
's Alan T. Waterman Award
.
, Austria
. He received his Ph.D. in 1982 from Graz University of Technology
, under the supervision of Hermann Maurer
; his thesis was entitled “Intersection Problems in Computational Geometry.” After a brief assistant professorship at Graz, he joined the faculty of the University of Illinois at Urbana-Champaign
in 1985, and moved to Duke University in 1999. In 1996, with his wife Ping Fu (then director of visualization at the National Center for Supercomputing Applications
), he co-founded Geomagic, a company that develops shape modeling software; he continues to serve on its board of directors. Since August 2009 he is Professor at the Institute of Science and Technology Austria (IST Austria) in Klosterneuburg.
In 1991, Edelsbrunner received the Alan T. Waterman Award. He was elected to the American Academy of Arts and Sciences
in 2005, and received an honorary doctorate from Graz University of Technology in 2006. In 2008 he was elected to the German Academy of Sciences Leopoldina.
.
He has also published two books on computational geometry: Algorithms in Combinatorial Geometry (Springer-Verlag, 1987, ISBN 9783540137221), and Geometry and Topology for Mesh Generation (Cambridge University Press, 2001, ISBN 9780521793094).
As Edelsbrunner's Waterman Award citation states,
Another heavily cited paper, also with Mücke, concerns “simulation of simplicity.” This is a technique for automatically converting algorithms that work only when their inputs are in general position
(for instance, algorithms that may misbehave when some three input points are collinear) into algorithms that work robustly, correctly, and efficiently in the face of special-position inputs.
Edelsbrunner has also made important contributions to algorithms for intersections of line segment
s, construction of K-set
s, the ham sandwich theorem
, Delaunay triangulation
, point location
, interval tree
s, fractional cascading
, and protein docking.
Computational geometry
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...
, the Arts & Science Professor of Computer Science and Mathematics at Duke University
Duke University
Duke University is a private research university located in Durham, North Carolina, United States. Founded by Methodists and Quakers in the present day town of Trinity in 1838, the school moved to Durham in 1892. In 1924, tobacco industrialist James B...
, Professor at the Institute of Science and Technology Austria
Institute of Science and Technology Austria
The Institute of Science and Technology Austria is an institute of basic research located in Klosterneuburg, close to Vienna . The draft concept was developed by the Austrian physicist Anton Zeilinger in 2002. Preparation work started in 2007...
(IST Austria), and the co-founder of Geomagic, Inc. He was the first of only two computer scientists to win the National Science Foundation
National Science Foundation
The National Science Foundation is a United States government agency that supports fundamental research and education in all the non-medical fields of science and engineering. Its medical counterpart is the National Institutes of Health...
's Alan T. Waterman Award
Alan T. Waterman Award
The Alan T. Waterman Award is the United States's highest honorary award for scientists no older than 35. It is awarded on a yearly basis by the National Science Foundation. In addition to the medal, the awardee receives a grant of $500,000 to be used for advanced scientific research at the...
.
Academic biography
Edelsbrunner was born in 1958 in GrazGraz
The more recent population figures do not give the whole picture as only people with principal residence status are counted and people with secondary residence status are not. Most of the people with secondary residence status in Graz are students...
, Austria
Austria
Austria , officially the Republic of Austria , is a landlocked country of roughly 8.4 million people in Central Europe. It is bordered by the Czech Republic and Germany to the north, Slovakia and Hungary to the east, Slovenia and Italy to the south, and Switzerland and Liechtenstein to the...
. He received his Ph.D. in 1982 from Graz University of Technology
Graz University of Technology
The Graz University of Technology is the second largest university in Styria, Austria, after the University of Graz. Austria has three universities of technology – in Graz, in Leoben, and in Vienna. The Graz University of Technology was founded in 1811 by Archduke John of Austria. TUG, as the...
, under the supervision of Hermann Maurer
Hermann Maurer
Hermann Maurer is an Austrian computer scientist, serving as Professor of Computer Science at the Graz University of Technology. He has supervised over 40 dissertations, written more than 20 books and over 600 scientific articles, and started or been involved with a number of...
; his thesis was entitled “Intersection Problems in Computational Geometry.” After a brief assistant professorship at Graz, he joined the faculty of the University of Illinois at Urbana-Champaign
University of Illinois at Urbana-Champaign
The University of Illinois at Urbana–Champaign is a large public research-intensive university in the state of Illinois, United States. It is the flagship campus of the University of Illinois system...
in 1985, and moved to Duke University in 1999. In 1996, with his wife Ping Fu (then director of visualization at the National Center for Supercomputing Applications
National Center for Supercomputing Applications
The National Center for Supercomputing Applications is an American state-federal partnership to develop and deploy national-scale cyberinfrastructure that advances science and engineering. NCSA operates as a unit of the University of Illinois at Urbana-Champaign but it provides high-performance...
), he co-founded Geomagic, a company that develops shape modeling software; he continues to serve on its board of directors. Since August 2009 he is Professor at the Institute of Science and Technology Austria (IST Austria) in Klosterneuburg.
In 1991, Edelsbrunner received the Alan T. Waterman Award. He was elected to the American Academy of Arts and Sciences
American Academy of Arts and Sciences
The American Academy of Arts and Sciences is an independent policy research center that conducts multidisciplinary studies of complex and emerging problems. The Academy’s elected members are leaders in the academic disciplines, the arts, business, and public affairs.James Bowdoin, John Adams, and...
in 2005, and received an honorary doctorate from Graz University of Technology in 2006. In 2008 he was elected to the German Academy of Sciences Leopoldina.
Publications
Edelsbrunner has over 100 research publications and is an ISI highly cited researcherISI highly cited researcher
ISI Highly Cited is a database of "highly cited researchers"—scientific researchers whose publications are most often cited in academic journals over the past decade, published by the Institute for Scientific Information...
.
He has also published two books on computational geometry: Algorithms in Combinatorial Geometry (Springer-Verlag, 1987, ISBN 9783540137221), and Geometry and Topology for Mesh Generation (Cambridge University Press, 2001, ISBN 9780521793094).
As Edelsbrunner's Waterman Award citation states,
Research contributions
Edelsbrunner's most heavily cited research contribution is his work with Ernst Mücke on alpha shapes, a technique for defining a sequence of multiscale approximations to the shape of a three-dimensional point cloud. In this technique, one varies a parameter alpha ranging from 0 to the diameter of the point cloud; for each value of the parameter, the shape is approximated as the union of line segments, triangles, and tetrahedra defined by 2, 3, or 4 of the points respectively such that there exists a sphere of radius at most alpha containing only the defining points.Another heavily cited paper, also with Mücke, concerns “simulation of simplicity.” This is a technique for automatically converting algorithms that work only when their inputs are in general position
General position
In algebraic geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the general case situation, as opposed to some more special or coincidental cases that are possible...
(for instance, algorithms that may misbehave when some three input points are collinear) into algorithms that work robustly, correctly, and efficiently in the face of special-position inputs.
Edelsbrunner has also made important contributions to algorithms for intersections of line segment
Line segment
In geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...
s, construction of K-set
K-set (geometry)
In discrete geometry, a k-set of a finite point set S in the Euclidean plane is a subset of k elements of S that can be strictly separated from the remaining points by a line. More generally, in Euclidean space of higher dimensions, a k-set of a finite point set is a subset of k elements that can...
s, the ham sandwich theorem
Ham sandwich theorem
In measure theory, a branch of mathematics, the ham sandwich theorem, also called the Stone–Tukey theorem after Arthur H. Stone and John Tukey, states that given measurable "objects" in -dimensional space, it is possible to divide all of them in half with a single -dimensional hyperplane...
, 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...
, 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 ....
, interval tree
Interval tree
In computer science, an interval tree is an ordered tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for example, to find all roads on a computerized map inside...
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...
, and protein docking.