Prof. Emo Welzl receives SoCG Test of Time Award
Professors Emo Welzl and David Haussler have received the Symposium of Computational Geometry (SoCG) Test of Time Award for a paper with long-term impact they published 34 years ago.
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.
About the Symposium of Computational Geometry (SoCG)
This year, the International Symposium on Computational Geometry (SoCG 2020), held for the 36th time, forms part of the Computational Geometry Week (CG Week). This international forum comprises several events, including the associated Media Exposition, workshops, the Young Researchers Forum, and the CG Challenge. As the premier conference for advances in computational geometry and its many applications, the 2020 edition will take place in Zurich, Switzerland from 23-26 June 2020. Read more