Emo Welzl | |
|---|---|
| Born | 4 August 1958  Linz |
| Alma mater | Graz University of Technology |
| Occupation | |
| Awards |
|
| Academic career | |
| Institutions |
|
| Doctoral advisor | Hermann Maurer |
| Doctoral students | József Solymosi |
Emmerich (Emo) Welzl (born 4 August 1958 in Linz, Austria) [1] is a computer scientist known for his research in computational geometry. He is a professor in the Institute for Theoretical Computer Science at ETH Zurich in Switzerland.
Welzl was born on 4 August 1958 in Linz, Austria. He studied at the Graz University of Technology receiving a Diplom in Applied Mathematics in 1981 and a doctorate in 1983 under the supervision of Hermann Maurer. [1] [2] Following postdoctoral studies at Leiden University, he became a professor at the Free University of Berlin in 1987 at age 28 and was the youngest professor in Germany. [3] Since 1996 he has been professor of Computer Science at the ETH Zurich. [1]
Welzl is a member of multiple journal editorial boards, and has been program chair for the Symposium on Computational Geometry in 1995, one of the tracks of the International Colloquium on Automata, Languages and Programming in 2000, and one of the tracks of the European Symposium on Algorithms in 2007. [1]
Much of Welzl's research has been in computational geometry. With David Haussler, he showed that machinery from computational learning theory including ε-nets and VC dimension could be useful in geometric problems such as the development of space-efficient range searching data structures. [4] He devised linear time randomized algorithms for the smallest circle problem [5] and for low-dimensional linear programming, and developed the combinatorial framework of LP-type problems that generalizes both of these problems. [6] Other highly cited research publications by Welzl and his co-authors describe algorithms for constructing visibility graphs and using them to find shortest paths among obstacles in the plane, [7] test whether two point sets can be mapped to each other by a combination of a geometric transformation and a small perturbation, [8] and pioneer the use of space-filling curves for range query data structures. [9]
Welzl won the Gottfried Wilhelm Leibniz Prize in 1995. [10] He was an Invited Speaker of the International Congress of Mathematicians in Berlin in 1998. [11] He was elected as an ACM Fellow in 1998, [12] as a member of the German Academy of Sciences Leopoldina in 2005, [13] of the Academia Europaea in 2006, [14] and of the Berlin-Brandenburg Academy of Sciences and Humanities in 2007. [15]
In mathematics, given a non-empty set of objects of finite extension in -dimensional space, for example a set of points, a bounding sphere, enclosing sphere or enclosing ball for that set is a -dimensional solid sphere containing all of these objects.
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, a coreset is a small set of points that approximates the shape of a larger point set, in the sense that applying some geometric measure to the two sets results in approximately equal numbers. Many natural geometric optimization problems have coresets that approximate an optimal solution to within a factor of 1 + ε, that can be found quickly, and that have size bounded by a function of 1/ε independent of the input size, where ε is an arbitrary positive number. When this is the case, one obtains a linear-time or near-linear time approximation scheme, based on the idea of finding a coreset and then applying an exact optimization algorithm to the coreset. Regardless of how slow the exact optimization algorithm is, for any fixed choice of ε, the running time of this approximation scheme will be O(1) plus the time to find the coreset.
Planarity is a 2005 puzzle computer game by John Tantalo, based on a concept by Mary Radcliffe at Western Michigan University. The name comes from the concept of planar graphs in graph theory; these are graphs that can be embedded in the Euclidean plane so that no edges intersect. By Fáry's theorem, if a graph is planar, it can be drawn without crossings so that all of its edges are straight line segments. In the planarity game, the player is presented with a circular layout of a planar graph, with all the vertices placed on a single circle and with many crossings. The goal for the player is to eliminate all of the crossings and construct a straight-line embedding of the graph by moving the vertices one by one into better positions.
The smallest-circle problem is a computational geometry problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane. The corresponding problem in n-dimensional space, the smallest bounding sphere problem, is to compute the smallest n-sphere that contains all of a given set of points. The smallest-circle problem was initially proposed by the English mathematician James Joseph Sylvester in 1857.
Kurt Mehlhorn is a German theoretical computer scientist. He has been a vice president of the Max Planck Society and is director of the Max Planck Institute for Computer Science.
In mathematics, a unique sink orientation is an orientation of the edges of a polytope such that, in every face of the polytope, there is exactly one vertex for which all adjoining edges are oriented inward. If a polytope is given together with a linear objective function, and edges are oriented from vertices with smaller objective function values to vertices with larger objective values, the result is a unique sink orientation. Thus, unique sink orientations can be used to model linear programs as well as certain nonlinear programs such as the smallest circle problem.
János Pach is a mathematician and computer scientist working in the fields of combinatorics and discrete and computational geometry.
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 Discrete and Computational Geometry and of the Journal of Computational Geometry.
In computational geometry, an ε-net is the approximation of a general set by a collection of simpler subsets. In probability theory it is the approximation of one probability distribution by another.
In combinatorial mathematics and extremal set theory, the Sauer–Shelah lemma states that every family of sets with small VC dimension consists of a small number of sets. It is named after Norbert Sauer and Saharon Shelah, who published it independently of each other in 1972. The same result was also published slightly earlier and again independently, by Vladimir Vapnik and Alexey Chervonenkis, after whom the VC dimension is named. In his paper containing the lemma, Shelah gives credit also to Micha Perles, and for this reason the lemma has also been called the Perles–Sauer–Shelah lemma and the Sauer–Shelah–Perles lemma.
In the study of algorithms, an LP-type problem is an optimization problem that shares certain properties with low-dimensional linear programs and that may be solved by similar algorithms. LP-type problems include many important optimization problems that are not themselves linear programs, such as the problem of finding the smallest circle containing a given set of planar points. They may be solved by a combination of randomized algorithms in an amount of time that is linear in the number of elements defining the problem, and subexponential in the dimension of the problem.
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.
Dmitry Feichtner-Kozlov is a Russian-German mathematician.
Bettina Speckmann is a German computer scientist who heads the Applied Geometric Algorithms group in the Department of Mathematics and Computer Science of Eindhoven University of Technology in Eindhoven, Netherlands, where she is a professor. The main topics of her research are computational geometry and information visualization, especially focusing on the geometry and visualization of objects in motion.
Deborah A. Joseph is an American computer scientist known for her research in computational geometry, computational biology, and computational complexity theory. She is a professor emeritus of computer science at the University of Wisconsin–Madison.
Peter Bürgisser is a Swiss mathematician and theoretical computer scientist who deals with algorithmic algebra and algebraic complexity theory.
In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle.
Shmuel Onn is a mathematician, Professor of Operations Research and Dresner Chair at the Technion - Israel Institute of Technology. He is known for his contributions to integer programming and nonlinear combinatorial optimization.
Helmut Alt is a German computer scientist whose research concerns graph algorithms and computational geometry. He is known for his work on matching geometric shapes, including methods for efficiently computing the Fréchet distance between shapes. He was also the first to use the German phrase "Algorithmische Geometrie" [algorithmic geometry] to refer to computational geometry. He is a professor of computer science at the Free University of Berlin.
| International | |
|---|---|
| National | |
| Academics | |
| People | |
| Other | |