Prof. Emo Welzl erhält den Symposium of Computational Geometry (SoCG) Test of Time Award
Die Professoren Emo Welzl (D-INFK) und David Haussler haben den Symposium of Computational Geometry (SoCG) Test of Time Award für ein Paper mit langfristiger Wirkung erhalten, das sie vor 34 Jahren veröffentlicht haben.
Das 1986 bei "Proceedings of the second annual symposium on Computational Geometry" veröffentlichte Paper "Epsilon-nets and simplex range queries" stellt grundlegende Werkzeuge für die Randomisierung in der algorithmischen Geometrie vor.
Die Autoren präsentierten eine neue Technik für die Abfrage im Halbraum und im Simplexbereich unter Verwendung von Ο (n) Raum und Ο (n ^ a) Abfragezeit, wobei a <d (d-1) / (d (d-1) + 1) + γ für alle Dimensionen d ≥ 2 und γ> 0. Diese Grenzen sind besser als die zuvor veröffentlichten für alle d ≥ 2. Die Technik verwendet Zufallsstichproben, um eine Partitionsbaumstruktur zu erstellen. Das Konzept eines ε-Netzes für einen abstrakten Satz von Bereichen wurde eingeführt, um das gewünschte Ergebnis dieser Zufallsstichprobe zu beschreiben und notwendige und ausreichende Bedingungen zu schaffen, unter denen eine Zufallsstichprobe ein ε-Netz mit hoher Wahrscheinlichkeit ist. Die Anwendung dieser Ideen auf andere Probleme mit Bereichsabfragen wird in diesem Paper veranschaulicht.
Prof. Welzl erhält den Test of Time Award sowie einen Best Paper Award (2020) für "Convex Hulls of Random Order Type" zusammen mit Xavier Goaoc auf der Computational Geometry Week im Juni 2020 in Zürich, der Schweiz.
Über Prof. Emo Welzl
Prof. Emo Welzl ist Professor am Institut für Theoretische Informatik, wo er zusammen mit Prof. Bernd Gärtner die "Theory of Combinatorial Algorithms Group" leitet. Prof. Welzl ist seit 1996 ordentlicher Professor für Informatik am Institut für Informatik der ETH Zürich. Seine Forschungsschwerpunkte liegen in den Grundlagen der Informatik, hauptsächlich Algorithmen und Datenstrukturen, insbesondere rechnergestützte Geometrie und Anwendungen, kombinatorische Modelle zur Optimierung , randomisierte Methoden und diskrete Geometrie.
Über das Symposium für Computergeometrie (SoCG):
In diesem Jahr findet das 36. Symposium für Computational Geometry (SoCG 2020) als Teil der Computational Geometry Week (CG Week) statt. Dieses internationale Forum umfasst mehrere Veranstaltungen, darunter die dazugehörige Medienausstellung, Workshops, das Young Researchers Forum und die CG Challenge. Als bedeutendste Konferenz für Fortschritte in der Computergeometrie und ihren zahlreichen Anwendungen findet die Ausgabe 2020 vom 23. bis 26. Juni 2020 in Zürich statt. Mehr Details