Prof. Emo Welzl erhält SoCG Test of Time-​Auszeichnung

The paper “Epsilon-nets and simplex range queries”, published at “Proceedings of the second annual symposium on Computational Geometry” in 1986 introduces fundamental tools for randomisation in computational geometry.

The authors presented a new technique for half-space and simplex range query using Ο(n) space and Ο(n^a) query time, where a < d(d-1)/(d(d-1) + 1) + γ for all dimensions d ≥ 2 and γ > 0. These bounds are better than those previously published for all d ≥ 2. The technique uses random sampling to build a partition-tree structure. The concept of an ε-net for an abstract set of ranges was introduced to describe the desired result of this random sampling and give necessary and sufficient conditions that a random sample is an ε-net with high probability. The application of these ideas to other range query problems is illustrated in the paper.

Prof. Welzl will receive the Test of Time Award, along with a best paper award for his 2020 paper “Convex hulls of random order types” with Xavier Goaoc at the Computational Geometry Week in Zurich, Switzerland in June 2020.

About Prof. Emo Welzl

Prof. Emo Welzl is a professor at the Institute for Theoretical Computer Science where he leads the Theory of Combinatorial Algorithms Group, together with Prof. Bernd Gärtner. Prof. Welzl has been full professor of computer science at the Department of Computer Science, ETH Zurich, since 1996. His research focuses on the foundations of computer science, mainly algorithms and data structures, in particular computational geometry and applications, combinatorial models for optimisation, randomized methods, and discrete geometry.